2020/08/24

[Algorithm] 너비 우선 탐색 BFS / 깊이 우선 탐색 DFS

개인적으로 어려워 하는 알고리즘,, 알고리즘 BFS는 FIFO를 원칙으로 하는 Queue로 구현한다. 탐색을 시작하는 첫 노드(root)를 queue에 넣고 탐색을 시작한다. A. queue에서 노드를 꺼낸다. B. 꺼낸 노드와 연결된 노드 중 방문하지 않은 노드를 방문하고 queue에 넣는다. queue에 노드가 없어질 때 까지 AB반복 구현 def bfs(graph, root): visit = list() queue = [root] #AB반복 while queue: temp = queue.pop(0) if temp not in visit: print(temp) visit.append(temp) queue.extend(graph[temp]) 알고리즘 DFS는 LIFO를 원칙으로 하는 Stack으로 구현..