Introduction
Coddy의 너비 우선 탐색 - 그래프 알고리즘 코스 레슨 — 9개 중 1번째.
그래프 알고리즘 시리즈에 다시 오신 것을 환영합니다! 깊이 우선 탐색(DFS)에 이어, 또 다른 기본적인 그래프 탐색인 너비 우선 탐색(BFS)에 대해 알아보겠습니다.
DFS가 깊게 파고든다면, BFS는 계층(layers)별로 탐색합니다. 먼저 시작 정점을 탐색하고, 그 다음 모든 이웃 정점들을, 그 다음에는 두 단계 떨어진 모든 정점들을 탐색하는 식입니다. 이러한 계층별 순서 덕분에 BFS는 가중치가 없는 그래프에서 최단 경로를 찾을 수 있습니다.
시리즈의 다른 부분과 마찬가지로, 그래프는 n(정점 개수, 0부터 n - 1까지)과 무방향 쌍의 평면 배열인 edges([u0, v0, u1, v1, ...])로 주어집니다.
시작해 봅시다!
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
