알고리즘1 너비 우선 탐색(BFS, Breadth-Fisrt Search) 너비 우선 탐색이란? - 루트 노드(or 다른 임의의 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다. - 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방법이다. BFS의 사용 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 주로 사용한다. BFS의 특징 재귀적으로 동작하지 않는다. 어떤 노드를 방문했었는지 반드시 검사해야 한다. 큐(Queue)를 사용한다. 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용하는 것이다. 'Prim', 'Dijkstra' 알고리즘과 유사하다. DFS보다 좀 더 복잡하다. BFS의 장점 노드의 .. 2022. 3. 15. 이전 1 다음
