너비 우선 탐색이란?
- queue을 이용
graph = {
'A' : ['E','C','B'],
'B' : ['A'],
'C' : ['A'],
'D' : ['E','F'],
'E' : ['D','A'],
'F' : ['D']
}
def bfs(graph,start) :
visited = list()
queue = list()
queue.append(start)
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
queue.extend(graph[node])
return visited
print(bfs(graph,'E'))
출력 : ['E', 'D', 'A', 'F', 'C', 'B']
def bfs(graph,start) :
visited = list()
queue = list()
queue.append(start)
count = 0
while queue:
node = queue.pop(0)
print(f'{count}번째 current : {node}')
if node not in visited:
visited.append(node)
queue.extend(graph[node])
print(f'{count}번째 visited : {visited}')
print(f'{count}번째 queue : {queue}')
print("")
count += 1
return visited
출력
0번째 current : E
0번째 visited : ['E']
0번째 queue : ['D', 'A']
1번째 current : D
1번째 visited : ['E', 'D']
1번째 queue : ['A', 'E', 'F']
2번째 current : A
2번째 visited : ['E', 'D', 'A']
2번째 queue : ['E', 'F', 'E', 'C', 'B']
3번째 current : E
3번째 current : F
3번째 visited : ['E', 'D', 'A', 'F']
3번째 queue : ['E', 'C', 'B', 'D']
4번째 current : E
4번째 current : C
4번째 visited : ['E', 'D', 'A', 'F', 'C']
4번째 queue : ['B', 'D', 'A']
5번째 current : B
5번째 visited : ['E', 'D', 'A', 'F', 'C', 'B']
5번째 queue : ['D', 'A', 'A']
6번째 current : D
6번째 current : A
6번째 current : A
최종 : ['E', 'D', 'A', 'F', 'C', 'B']