Breadth-First Search
개요
- Graph 의 탐색 방법인 Breadth-First Search (너비우선탐색) 알고리즘에 대해 알아본다
- Breadth-First Search 메소드 구현
- 코드 보기
Breadth-First Search (너비우선탐색)
그래프 또는 트리의 탐색에는 크게 깊이우선탐색, 너비우선탐색 두가지 방법이 있다. 탐색이라하면 각 vertex 들을 한번씩만 거치고 모든 vertex 를 순회하는 것을 말한다. 이번 포스팅에서 볼 내용은 너비우선탐색 (BFS) 이다.
이번 포스팅에서 BFS 에 사용할 그래프는 인접리스트를 이용해 위와같이 표현할 수 있다.
DFS 는 방문하지 않은 노드를 stack 에 넣는데 (재귀호출로 call stack 을 사용하든 직접 stack 에 넣든 stack 을 사용하는 방식이다), BFS 는 방문하지 않은 노드를 queue 에 넣어 구현한다.
BFS 는 Dijkstra 알고리즘에서 최단거리를 구할 때에도 쓰인다
source 인 s 를 시작으로 BFS 는 아래와 같이 동작한다.
- s 를 큐에 넣고 방문했음을 표시한다.
- 아래 과정을 큐가 비워질 때 까지 반복한다.
- 가장 덜 최근에 (least recently) 들어온 노드 v 를 꺼낸다.
- v 의 연결리스트에서 방문하지 않은 노드들을 큐에 넣으면서 방문했다고 표시한다.
아래는 동작하는 방식을 단계별로 표현한 슬라이드이다.
- 소스인 0 번을 큐에 넣고 시작한다.
- 0 번을 큐에서 꺼내면서 0 번에 연결된 2, 1, 5 노드 중 방문하지 않은 노드를 방문하면서 방문했음을 표시하고 차례대로 큐에 넣는다.
- 2 번을 큐에서 꺼내면서 2 번에 연결된 0, 1, 3, 4 노드 중 방문하지 않은 노드를 방문하면서 방문했음을 표시하고 차례대로 큐에 넣는다.
- 0, 1 번은 방문했으므로 3, 4 에 대해서 같은과정을 반복한다.
- 위 과정을 큐가 빌때까지 큐에서 차례로 꺼내는 노드들에 대해서 반복한다.
구현 - Java
public void bfs(int s) {
Queue<Integer> q = new LinkedList<>();
q.add(s);
marked[s] = true;
while (!q.isEmpty()) {
int v = q.poll(); // 자바의 Queue 에서 dequeue 하는 메소드
System.out.println(v);
for (int w : adj(v)) {
if (!marked[w]) {
q.add(w); // 자바의 Queue 에서 enqueue 하는 메소드
marked[w] = true;
edgeTo[w] = v;
}
}
}
}
