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

시작 노드(루트 노드)에서부터 가까운 정점을 먼저 방문하고, 멀리 있는건 나중에 방문하는 방법.

간단히 정리해서 큐를 이용하면 BFS를 구현할 수 있다.

구현 방법

1. 루트 노드를 큐에 넣는다.
2. 현재 큐의 노드를 빼서 visited에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2부터 반복!
5. 큐가 비어있을 경우에 반복문을 종료한다.

구현해보기

• 전체코드

1. 시작 노드를 방문 리스트, 큐에 넣는다.

   def bfs_deque(start):
   	visited = [start]
   	q = deque([start])
   

2. 큐가 있는 동안 반복문 실행하여 인접 노드를 탐색한다.

   while q :
   	node = q.leftpop()        # 루트노드 (시작노드)
   	for adj in graph[node]:   # 인접노드 방문 시작
   

3. 방문하지 않은 인접노드는 방문처리를하고 큐에 넣는다.

       while q:
           node = q.popleft()
           for adj in graph[node]:
               if adj not in visited:
                   q.append(adj)
                   visited.append(adj)