너비 우선 탐색1 [Java] BFS 너비 우선 탐색 - 인접리스트 / 인접행렬로 구현 BFS 너비 우선 탐색(Breadth First Search) "꼼꼼하게 좌우를 살피며 다니자"와 같이 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이다. 시작 정점을 지나고 나면 깊이가 1인 모든 정점을 방문하고, 그다음에는 깊이가 2인 모든 정점을 방문한다. 이런 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점들을 방문해 나가다가 나중에는 더 이상 방문할 곳이 없을 때 탐색을 종료한다. * 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 * 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. BFS의 특징 BFS는 시작 정점으로부터 거리가 가까운 정점의 순서.. 2020. 5. 9. 이전 1 다음 반응형
