18. BFS (너비 우선 탐색)
알고리즘 공부
2019. 10. 6.
BFS (너비 우선 탐색, Breadth-First Search) 그래프 탐색. 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 너비 우선 탐색. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. BFS(너비 우선 탐색)이 DFS(깊이 우선 탐색)보다 좀 더 복잡하다. 너비 우선 탐색(BFS)의 특징. 직관적이지 않은 면이 있다. BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐..
