깊이 우선 탐색
스택구조(혹은 재귀)
1->2->7->6->8
1->2->7->6
1->2->7
1->2
1
1->3->4->5
즉, 1->2->7->6->8->3->4->5
너비 우선 탐색 가까운 노드부터 우선적으로 탐색하는 알고리즘
큐 자료구조
1에서 시작
즉,1->2->3->8->7->4->5->6
from collections import deque
import turtle
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v,end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i]=True
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
bfs(graph,1,visited)