알고리즘 - 너비 우선 탐색 (Breadth First Search)

알고리즘 - 너비 우선 탐색 (Breadth First Search)

BFS는 Breadth First Search, 너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

 

[ BFS 활용 ]

최단경로 찾기, 위상정렬 등

 

[ pseudocode로 BFS 구현 ]

BFS(G, s)
    for each vertex u ∈ G.V - {s}  //초기화 작업
        u.color = WHITE				//s를 제외한 모든 정점의 상태를 white로,
        u.d = ∞						//거리를 무한대로
        u.𝝅 = NIL					 //선행자를 NIL로 초기화
    s.color = GRAY	//시작 정점 s의 상태를 gray로
    s.d = 0			//거리를 0으로
    s.𝝅 = NIL		 //선행자를 NIL로 초기화
    Q = ∅			
    ENQUEUE(Q,s)	//그리고 큐에 s를 추가
    while Q != ∅		//Q가 비어있게 될 때 까지 반복문 수행
        u = DEQUEUE(Q)	//매 수행마다 큐에서 정점을 하나씩 뺌
        for each v ∈ G.Adj[u]	//인접한 모든 정점에 대하여
            if v.color == WHITE	 //각 정점의 상태가 white이면
                v.color = GRAY	 //상태를 gray로 바꾸고
                v.d = u.d + 1	 //거리를 이전 정점의 거리에서 1을 더하고
                v.𝝅 = u		  //선행자를 이전 정점으로 한다
                ENQUEUE(Q,v) 
            //만약 인접한 정점의 상태가 white가 아니라면 아무일도 일어나지 않고 다음 인접한 정점을 검사
        u.color = BLACK //모든 인접한 정점을 확인했으면, u는 더 이상 방문할 정점이 없으므로 상태를 black으로 바꿈

 

[ 시간 복잡도 ]

if v.color == white의 부분은 |E|만큼 수행되고, 그 내부는 |V|만큼의 시간이 걸린다.

따라서  θ(V + E)의 시간복잡도가 나온다.

 

[ 동작 과정 ]

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

[ 코드 ]

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    while queue:
    	v = queue.popleft()
        print(v, end=" ")
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7], 
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)

# 1 2 3 8 7 4 5 6