너비 우선 탐색(BFS)
그래프를 한 층씩 탐색합니다. 다음 정점은 큐가 정하므로 항상 가까운 정점부터 방문합니다.
- 시간 O(V + E)
- 메모리 O(V)
- 큐 사용
용어 설명
- 정점: 그래프의 점. 여기서는 글자가 적힌 원으로 그립니다.
- 간선: 두 정점을 잇는 선. 여기서는 양쪽 방향으로 다닐 수 있습니다.
- 이웃: 한 정점과 간선으로 이어진 정점들. 알파벳 순서로 살펴봅니다.
- 큐: 먼저 들어간 것이 먼저 나옵니다. BFS는 항상 가장 오래 기다린 정점을 꺼냅니다.
- 스택: 마지막에 들어간 것이 먼저 나옵니다. DFS는 항상 가장 최근에 도착한 정점에서 계속 나아갑니다.
- V와 E: 정점과 간선의 개수. O(V + E)는 모든 정점과 간선을 정해진 횟수만큼만 처리한다는 뜻입니다.
0 / 60 단계
- 큐에 있음
- 현재
- 완료
- 탐색 트리 간선
- 건너뛴 간선
A에서 시작합니다. 재생을 누르거나 한 단계씩 진행하세요.
스페이스바: 재생 또는 일시정지. 좌우 화살표 키: 단계 이동. Home과 End 키: 처음과 끝으로 이동.
해 보세요: 두 부분으로 된 그래프를 골라 보세요. 시작 정점과 이어지지 않은 정점에는 끝까지 닿지 않습니다.
작동 방식
BFS는 시작 정점을 큐에 넣습니다. 그런 다음 큐 앞의 정점을 꺼내고, 그 정점의 새 이웃을 큐 뒤에 넣는 일을 되풀이합니다. 큐는 도착한 순서대로 처리하므로, 간선 하나 거리의 정점은 모두 간선 두 개 거리의 정점보다 먼저 완료됩니다. 정점 옆의 숫자는 시작 정점에서의 거리, 즉 그 정점까지 가는 데 필요한 가장 적은 간선 수입니다.
언제 쓰면 좋을까
단계 수로 가장 짧은 길이 필요할 때 BFS를 쓰세요. 퍼즐의 최소 이동 횟수, 네트워크의 최소 홉 수, 두 다리 안에 아는 사람 찾기 같은 경우입니다. 큰 그래프에서는 큐가 한 층 전체를 한꺼번에 담기 때문에 길어질 수 있습니다.