그래프에서의 BFS

Graph Traversal

그래프 순회

- 순회 (traversal)

그래프의 모든 노드들을 방문하는 일을 말한다.

- 순회를 하는 두 가지 방법

BFS (Breadth-First Search, 너비 우선 순회)

DFS (Depth-First Search, 깊이 우선 순회)

너비 우선 순회 (BFS)

- BFS 알고리즘은 아래와 같은 순서로 노드들을 방문하게 된다.

$L_0$ = {s} (s : 출발 노드)

$L_1$ = $L_0$의 모든 이웃 노드들

$L_2$ = $L_1$의 이웃들 중 $L_0$의 이웃에 속하지 않은 노드들

...

$L_i$ = $L_{i-1}$의 이웃들 중에 $L_{i-2}$에 속하지 않는 노드들

*level order은 BFS의 이진 트리 버전이다.

큐를 이용한 너비 우선 순회

1) check the start node; // check는 이미 방문한 노드라는 것을 표시한다는 뜻이다.

2) insert the start node into the queue;

3) while queue is not empty

remove a node v from queue;

for each unchecked neighbor w of v

check and insert w into the queue;

BFS와 최단 경로에 대해

- s에서 $L_i$에 속한 노드까지 최단 경로의 길이는 i이다. (결로의 길이는 경로에 속한 엣지의 개수를 의미한다.)

- BFS를 진행하며 각 노드에 대한 최단 경로의 길이를 구할 수 있게 된다.

- 입력 : 방향 혹은 무방향 그래프 G = (V, E), 출발 노드 s ∈ V

- 출력 : 모든 노드인 v에 대하여

d[v] = s부터 v까지 최단 경로의 길이 (엣지의 개수)

π[v] = s부터 v까지 최단 경로 상에서 v의 직전 노드를 의미한다.

BFS 구현 코드

BFS (G, s) // G : 그래프, s : 출발 노드

Q <- ∅;

d[s] <- 0; // 최단 경로의 길이를 0으로 초기화

π[s] <- null; // predecessor를 null로 초기화

Enqueue (Q, s);

while Q ≠ ∅

u <- Dequeue (Q);

for each v adjacent to u // 보통은 모든 노드에 대해 d[v]를 -1로 초기화한 후 -1이면 미방문, 아니면 방문으로 판단.

if v is unvisited

mark v as visited;

d[s] <- d[u] + 1;

π[s] <- u; // u를 v의 predecessor로 설정한다.

Enqueue (Q, v);

- 개선

BFS (G, s)

Q <- ∅;

for each node u

d[u] <- -1;

π[u] <- null;

d[s] <- 0; π[s] <- null;

Enqueue (Q, s);

while Q ≠ ∅ // while문을 한 번 반복할 때마다 큐에서 하나를 꺼내기 때문에 최대 n번 반복한다.

u <- Dequeue (Q);

for each v adjacent to u // 인접리스트로 구현할 경우 for문은 각 노드 v에 대해 degree(v)번 돈다.

if d[v] == -1

d[v] <- d[u] + 1;

π[v] <- u;

Enqueue (Q, v); //unchecked 노드만 큐에 들어갈 수 있기에 어떤 노드들도 큐에 두 번 들어가지는 않는다.

-> 인접리스트로 구현할 때의 시간복잡도는 $\sum _{ v }{ degree(v) }$ = 2m이므로 O(n + m)의 시간 복잡도를 가진다.

- BFS를 이용하여 각 노드의 d와 π값을 계산한 결과 그래프

BFS 트리

- 각 노드 v와 π[v]를 연결하는 엣지들로 구성된 트리이다.

- BFS트리에서 s부터 v까지의 경로는 곧 s에서 v까지 가는 최단경로이다.

- 어떠한 엣지도 2개의 레이어를 건너가지 않는다.

(동일 레이어의 노드를 연력하거나 1개의 레이어를 건너간다.

BFS : 최단 경로 출력하기

PRINT-PATH (G, s, v)

if v == s

print s;

else if  π[v] == null

print "no path from s to v exists";

else

PRINT-PATH (G, s, π[v]);

print v;

- 그래프가 disconnected이거나 방향 그래프라면 BFS를 사용했을 때 모든 노드를 방문하지 않을 수 있다.

- 이 때는 BFS를 반복하여 모든 노드를 방문하게 한다.

BFS-ALL (G)

while there exists unvisited node v

BFS(G, v);