[CLRS] [20-2] BFS(Breadth-first search)

1. BFS?

- BFS는 인접한 노드를 우선 방문하는 것을 의미한다.

- Level-order 순회와 동일하다.

- Queue로 구현이 가능하다.

 

- 4를 기준으로 BFS를 한다고 생각해보자. (단 인접노드는 작은값부터 탐색한다.)

- walk는 다음과 같다.

- (4 -> (2 -> 3 -> 5)-> (0 -> 1) -> 6)

2. Code 구현

from collections import deque
def BFS(graph,start_node):
    visit = list()
    queue = deque()
    visit.append(start_node)
    queue.append(start_node)
    while len(queue) > 0 :
        for each_node in graph[queue[0]]:
            if (each_node in visit) == False:
                visit.append(each_node)
                queue.append(each_node)
        queue.popleft()
    return visit

graph = {0:[1,2],
         1:[0,2,3],
         2:[0,1,4],
         3:[1,4],
         4:[2,3,5],
         5:[4,6],
         6:[5]}

print(BFS(graph,4))


------------------------------------------------------------------------
Output

[4, 2, 3, 5, 0, 1, 6]