Breadth-first search

KVV·2024년 11월 19일

알고리즘

Distance: 두 vertex 사이에 존재하는 edge의 개수
Graph가 adjacency list를 사용한다고 가정하자.

BFS (Level by Level)

Undirected Graph를 예시로 들어보자.

discover: source vertex로부터 reachable 한 vertexs

distance 기준으로 오름차순으로 reachable한 vertex를 정렬하는 것이 목표이다.

Setting of BFS

Predecessor subgraph of G: $G_\pi = (V_\pi, E_\pi)$

$V_\pi = \{v \in V : v.\pi \neq \text{NIL}\} \cup \{s\}$
- Connected를 보장하기 위해 source vertex를 제외하고 $v.\pi \neq \text{NIL}$ 인 vertex를 포함
$E_\pi = \{(v.\pi, v) : v \in V_\pi - \{s\}\}$
- $|E_\pi| = |V_\pi| - 1$
- Connected graph에서 $|E| = |V| - 1$ 이므로 $E_\pi$ 는 tree edges 라고 할 수 있다.
$G_\pi$ 는 Breadth-first tree 이다.

Pseudo code of BFS

BFS (G, s)
1.	  for each vertex u in G.V - {s}
2.    	  u.color = WHITE
3.        u.d = inf
4.        u.π = NIL
5.    s.color = GRAY
6.    s.d = 0
7.    s.π = NIL
8.    Q = ∅
9.    ENQUEUE(Q, s)
10.   while Q is not ∅
11.       u = DEQUEUE(Q)
12.       for each v in G.Adj[u]
13.           if v.color == WHITE
14.            	   v.color = GRAY
15.                v.d = u.d + 1
16.                v.π = u
17.                ENQUEUE(Q, v)
18.       u.color = BLACK

$u.d$ : source vertex로부터의 distance
$u.\pi$ : 이전 vertex

Dynamic programming 등에서 path를 확인하기 위해 필요하다.

Line 1 ~ 9: Initial setting
Line 10 ~ 18: Graph Exploration

BFS 과정

Programmer의 이해를 위해 색깔을 이용한다.
discover 되면 queue의 들어감을 생각하자.

WHITE: 아직 discovered 되지 않은 vertex로, 아직 queue에 들어간 적이 없는 vertex .
GRAY: discovered 된 vertex로, 아직 queue에 존재하는 vertex.
BLACK: discovered 된 vertex로, queue에 들어갔다 빠져나와 정렬이 완료된 vertex

과정

GRAY vertex에 adjacency한 vertex를 모두 들려 vertex.color == WHITE라면 color = GRAY, distance += 1, $\pi$ 모두 변화시킨다.
- $\pi$ : adjacency 기준 vertex로 세팅
- distance: 이전 vertex + 1
- BLACK 이라면 skip
해당 vertexs를 Queue에 push 한다.
한 vertex에 adjacency vertex 더 이상 없다면 vertex color를 BLACK으로 바꾸고 DEQUEUE 된 vertex에 대해 (1) ~ (3) 과정을 반복한다.
Queue가 비었다면 종료한다.

predecessor subgraph of BFS

Tree이다.

$|E| = |V| - 1$

Color 정보가 반드시 필요할까?

Color 정보는 programmer의 이해를 돕기 위해 도입한 것

WITHE와 GRAY를 이용하여 모든 구분이 가능하기 때문에 BLACK은 사실상 필요없다.
한 번 Queue에 들어오고 나간 것은 다시 들어오지 않기 때문이다.

Color 정보를 사용하지 않는 BFS

BFS (G, s)
1.	  for each vertex u in G.V - {s}
2.        u.d = inf
3.        u.π = NIL
4.    s.d = 0
5.    s.π = s // 수정 1
6.    Q = ∅
7.    ENQUEUE(Q, s)
8.    while Q is not ∅
9.       u = DEQUEUE(Q)
10.       for each v in G.Adj[u]
11.           if v.π == NIL // 수정 2, V.d == inf도 사용 가능
12.                v.d = u.d + 1
13.                v.π = u
14.                ENQUEUE(Q, v)

Running time of BFS

전체 Running time은 $O(V + E)$ 이다.

Initialization: $\theta(V)$
Exploring the graph: $O(V + E)$
- 모든 edge는 최대 2번 explored 된다.
  - Directed graph의 경우 최대 한번
  - Undirected graph의 경우 최대 두번
  - $O(2E) = O(E)$
- 모든 vertex는 최대 한번 examined 된다.
  - 한번 discovered 된 vertex는 다시 탐색하지 않는다.
  - 즉, Queue에 최대 한번 들어간다.
  - 이를 위해 BLACK을 사용했다.

여기서 $E, V$ 는 $G_\pi$ 의 $E, V$ 가 아닌 $G$ 의 $E, V$ 이다.
- $O(E)$ : source vertex로부터 방문하지 않을 edge 또는 vertex가 있을 수 있기 때문에 $\theta$ 가 아닌 $O$ 이다.

Running time analysis on pseudo code

BFS (G, s)
1.	  for each vertex u in G.V - {s}
2.    	  u.color = WHITE
3.        u.d = inf
4.        u.π = NIL
5.    s.color = GRAY
6.    s.d = 0
7.    s.π = NIL
8.    Q = ∅
9.    ENQUEUE(Q, s)
10.   while Q is not ∅
11.       u = DEQUEUE(Q)
12.       for each v in G.Adj[u]
13.           if v.color == WHITE
14.            	   v.color = GRAY
15.                v.d = u.d + 1
16.                v.π = u
17.                ENQUEUE(Q, v)
18.       u.color = BLACK