[자료구조] Graph에서의 BFS

1. BFS(Breadth-First Search)란?

BFS(Breadth-First Search, 너비 우선 탐색)는 방문한 vertex와 인접한 vertex를 queue에 넣고 FIFO 순서로 탐색하는 탐색 방식이다.
트리에서 BFS 방식으로 탐색을 하면 같은 계층에 있는 노드를 우선으로 탐색한다.

2. BFS의 Pseudo Code

procedure BFS(G, start_v) is
	let Q be a queue
    label start_v as discovered
    Q.enqueue(start_v)
    
    while Q is not empty do
    	v := Q.dequeue()
        if v is the goal then
        	return v
        for all edges from v to w in G.adjacentEdges(v) do
        	if w is not labeled as discovered then
            	label w as discovered
                w.parent := v
                Q.enqueue(w)

3. 예시

왼쪽 그림과 같은 그래프가 있고, 시작 vertex가 1이라고 하자. visited 배열은 각 index의 vertex의 방문 여부를 의미한다.

먼저, 1을 방문하므로 visited[1]을 1로 바꾸고, 1을 queue에 넣는다.

queue에 있는 1을 빼고, 1의 인접 노드인 2와 4를 queue에 넣는다.

queue의 맨 앞에 있는 2를 빼고, 2의 인접 노드인 3과 6을 queue에 넣는다. 이때 1도 2의 인접 노드이지만, 1은 이미 방문했으므로 queue에 넣지 않는다. 그리고 visited[2]를 1로 바꾼다.

queue의 맨 앞에 있는 4를 빼고, 4의 인접 노드인 1과 6은 이미 방문했으므로 queue에 넣지 않는다. 그리고 visited[4]를 1로 바꾼다.

queue의 맨 앞에 있는 3을 빼고, 3의 인접 노드 중 아직 방문하지 않은 5를 queue에 넣는다. 그리고 visited[3]을 1로 바꾼다.

queue의 맨 앞에 있는 6을 빼고, 6의 인접 노드인 2, 4는 이미 방문했으므로 queue에 넣지 않는다. 그리고 visited[6]을 1로 바꾼다.

마지막으로 queue의 맨 앞에 있는 5를 빼고, 5의 인접 노드인 3은 이미 방문했으므로 queue에 넣지 않는다. 그리고 visited[5]를 1로 바꾼다.

이렇게 탐색을 진행하다가, queue에 아무 것도 남지 않게 된다면 탐색을 종료한다.

4. 시간복잡도

• queue에 값을 넣을 때 인접 노드 탐색
  • Adjacency matrix 사용: $O(n)$
  • Adjacency lists 사용: $O(\text{vertex degree})$
• 총 시간: $O(mn)$(m: 탐색된 component에 있는 vertex의 개수)

5. 특징

• DFS(Depth-First Search, 깊이 우선 탐색)와 같은 시간 복잡도를 가진다.
• Path finding, connected component 찾기, spanning tree 찾기에서 사용된다.