[그래프]BFS(너비 우선 탐색) 구현 방법을 알아보자

BFS는 큐를 이용한 반복 구조로 구현한다.

먼저 큐를 이용한 BFS Pseudo code를 보면서 어떻게 구현해야할지 생각해보자.

 

1) 큐를 이용한 BFS Pseudo code

 

BFS(G, start_v)
	    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)

 

2) 큐를 이용한 Python code

def iterative_bfs(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
    	v = queue.pop(0)
        for w in graph[v]:
        	if w not in discovered:
            	discovered.append(w)
                queue.append(w)
	return discovered

 

BFS는 재귀적으로 동작하지 않는다. 따라서 큐를 이용한 반복 구현만 가능하다.

코딩 테스트에서 재귀로 잘못 접근하지 않도록 주의가 필요하다.