그래프 - 너비우선탐색(BFS)

같은 레벨의 노드부터 먼저 탐색

 

BFS 구현

from collections import deque

#BFS
def bfs(graph, start):
	#시작점 start가 들어간 방문목록 visted로 초기화
    visited = [start]
   
    queue = deque([start])#방문할 노드 목록 queue에 시작점을 담아준다.

    while queue:#방문할 목록이 없을때까지 반복한다.
        current = queue.popleft()#방문할 목록에서 방문할 곳을 하나씩 꺼낸다.
        for k in graph[current]:#방문할 노드에 연결된 노드를 방문하고 다음 방문할 목록에 추가해준다. 
            if k not in visited:#방문한 곳이 아니면 방문하고 방문할 목록에 추가
                visited.append(k)#방문한 목록에 추가
                queue.append(k)#방문할 목록에 추가
    return visited#방문한 목록을 return

graph = {
    'A' : ['B', 'D', 'E'],
    'B' : ['A', 'C', 'D'],
    'C' : ['B'],
    'D' : ['A', 'B'],
    'E' : ['A']
}




print(bfs(graph, 'A'))# 결과 >>> ['A', 'B', 'D', 'E', 'C']