[알고리즘] 너비 우선 탐색 (BFS)

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

그래프 탐색이란?

• 하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한번 씩 방문하는 것
  EX) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는 지

너비 우선 탐색(BFS, Breadth-Firsh Search)

너비 우선 탐색(BFS) 란?

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
• 즉 깊게(deep) 탐색하기 전에, 넓게(wide) 탐색하는 것이다.
• 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
  - Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
  • 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
  • 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
• 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

너비 우선 탐색(BFS) 의 특징

• 직관적이지 않은 면이 있다.
  - BFS는 시작노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
• BFS는 재귀적으로 동작하지 않는다.
• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 만드시 검사해야 한다 는 것이다.
  - 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue)를 사용한다.
  - 즉 선입선출(FIFO) 원칙으로 탐색
  • 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
• 'Prim', 'Dijkstra' 알고리즘과 유사하다.

너비 우선 탐색(BFS)의 과정

깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더이상 방문할 곳이 없으면 탐색을 마친다.

1. a노드(시작노드)를 방문한다. (방문한 노드 체크)

• 큐에 방문된 노드를 삽입(enqueue)한다.
• 초기 상태의 큐에는 시작 노드만이 저장.
  - 즉, a노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃을 방문한다.

2. 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.

• 큐에서 꺼낸 노드를 방문한다.
• 큐에서 꺼낸 노드와 인접한 노드들을 모두 방문한다.
  - 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다.(dequeue)

3. 큐가 소진될 떄 까지 계속한다.

너비 우선 탐색(BFS)의 구현

• 구현 방법
  - 자료구조 큐 이용
• BFS의 의사코드(pseudocode

void bfs(Node root){
	Queue queue = new Queue();
    root.marked = true; //방문한 노드 체르
    queue.enqueue(root); //1-1. 큐의 끝에 추가
    
    //3. 큐가 소진될때까지 계속
    while(!queue.isEmpty()){
    	Node r= queue.dequeue(); //큐의 앞에서 노드 추출
        visit(r); //2-1. 큐에서 추출한 노드 방문
        //2-2. 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문
        foreach(Node n in r.adjacent){
        	if(n.marked == false){
            	n.marked = true;
                queue.enqueue(n);
            }
        }
    }
}

• BFS 구현

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define MAXV 5
using namespace std;

vector<int> adj[MAXV]; //그래프의 연결 관계를 인접리스트로 저장
int visit[MAXV] = { 0 }; // 노드 i를 방문한 적이 있으면 1, 없으면 0

void bfs(int start) {

	queue<int> q;

	//시작 노드의 번호 0이라고 가정
	q.push(start);
	visit[start] = 1;

	//queue가 비어있지 않은 동안
	while (!q.empty()) {

		//queue의 가장 앞에 있는 노드를 pop
		int here = q.front();
		q.pop();
		printf("%d ", here);

		//현재 노드에 인접한 모든 노드들 중
		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i];
			//아직 방문하지 않은 노드들을 queue에 push
			if (visit[there] == 0) {
				q.push(there);
				visit[there] = 1;
			}
		}
	}
}

int main() {
	adj[0].push_back(1);
	adj[1].push_back(0);
	adj[0].push_back(2);
	adj[2].push_back(0);
	adj[0].push_back(4);
	adj[4].push_back(0);

	adj[1].push_back(2);
	adj[2].push_back(1);

	adj[2].push_back(3);
	adj[3].push_back(2);
	adj[2].push_back(4);
	adj[4].push_back(2);

	adj[3].push_back(4);
	adj[4].push_back(3);
	
	bfs(0);

	return 0;
}

너비 우선 탐색(BFS)의 시간복잡도

• 인접 리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)
• 깊이 우선 탐색과 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.