22. Elementary Graph Algorithms

이 장에서는 그래프의 표현과 그래프 탐색에 대해 다룬다.

22.1. Representations of graphs

인접 리스트로 표현하는 것은 희박 그래프 (간선의 수가 정점의 수의 제곱보다 훨씬 적을 경우)에 좋고 인접 행렬로 표현하는 것은 조밀 그래프 (간선의 수가 정점의 수의 제곱에 가까울 경우)에 좋다. 인접 리스트 표현은 각 정점마다 그로부터 연결된 다른 정점의 번호가 있는 배열로 표현된다. 가중치 함수에 의해 가중치가 부여된 가중치 그래프의 경우 가중치를 같이 저장한다. 인접 행렬 표현은 정점 x 정점 크기의 행렬에 연결 여부를 표현한다. 똑같이 가중치를 저장할 수 있다.

Representing attributes

정점, 간선, 그래프의 특성을 저장하는 방법은 프로그래밍의 구현에 따라 다르다.

22.2. Breadth-first search

넓이 우선 탐색은 그래프 탐색의 가장 기본적인 알고리즘이다. 그래프와 시작점 s가 주어져 있을 때 깊이 우선 탐색은 s로부터 도달 가능한 모든 정점을 탐색하고 그 최단 거리를 계산한다. 이를 위해 모든 정점은 흰색으로부터 시작하고 그것이 최초로 발견되었을 때 색이 바뀐다. 회색과 검은색의 차이는 정점은 주위의 모두가 발견된 경우에만 검은색이 된다는 것이다. 넓이 우선 트리에서 흰색 정점이 새롭게 발견될 경우 그 정점을 발견한 간선의 시작점을 발견된 정점의 전임 또는 부모로 지칭한다. 구현은 다음과 같다.

BFS(G, s)
for each vertex u ∈ G.V - {s}
    u.color = WHITE
    u.d = ∞
    u.π = NIL
s.color = GRAY
s.d = 0
s.π = NIL
Q = Φ
ENQUEUE(Q, s)
while Q ≠ Φ
    u = DEQUEUE(Q)
    for each v ∈ G.Adj[u]
        if v.color == WHITE
            v.color = GRAY
            v.d = u.d + 1
            v.π = u
            ENQUEUE(Q, v)
    u.color = BLACK

Analysis

수행 시간은 O(V + E)이다.

Shortest paths

넓이 우선 탐색은 최단 경로의 길이인 최단 경로 거리를 찾는다.

Lemma. G = (V, E)가 그래프고 s가 G 내의 정점일 때 G 내의 임의의 간선 (u, v)에 대해 \delta(s, v) \leq \delta(s, u) + 1이다.

Lemma. G = (V, E)가 그래프고 G 내의 정점 s로부터 BFS를 수행했을 때 v.d \geq \delta(s, v)이다.

Lemma. G = (V, E)가 그래프고 BFS 수행 중일 때, Q의 원소들을 나열한 것이 v_{1}, \cdots, v_{r}이라 하면 v_{r}.d \leq v_{1}.d + 1이며 v_{i}.d \leq v_{i+1}.d이 성립한다.

Corollary. BFS 중에 v_{i}v_{j}보다 먼저 큐에 삽입된다면 v_{i}.d \leq v_{j}.d이다.

Theorem. G = (V, E)가 그래프고 G 내의 정점 s로부터 BFS를 수행했을 때 BFS는 s로부터 도달 가능한 모든 정점을 발견하며, 종료된 시점에서 v.d = \delta(s, v)이다. 또한, v가 s로부터 도달가능할 때 s에서 v로 가는 최단경로 중 하나는 s로부터 v.π로 가는 최단경로에 간선 (v.π, v)를 더한 것이다.

Breadth-first trees

G = (V, E)가 그래프고 정점 s가 있을 때 G의 전임 부분그래프 G_{\pi} = (V_{\pi}, E_{\pi})V_{\pi} = \{v \in V : v.\pi \neq NIL\} \cup \{s\}, E_{\pi} = \{(v.\pi, v) : v \in V_{\pi} - \{s\}\}로 정의된다. V_{\pi}가 s로부터 도달가능한 정점으로 이뤄지고 G_{\pi}가 s에서 v로의 유일한 단순 경로를 포함하고 그것이 s에서 v로 가는 G 내의 최단 경로인 경우 이는 넓이 우선 트리가 된다. 이 때 E_{\pi}트리 간선이라 한다.

Lemma. 그래프 G = (V, E)에 BFS를 적용하면 생성되는 전임 부분 그래프는 넓이 우선 트리이다.

이를 이용하여 최단 경로를 다음과 같이 출력할 수 있다.

PRINT-PATH(G, s, v)
if v == s
    print s
elseif v.π == NIL
    print "no path from " s " to " v " exists"
else
    PRINT-PATH(G, s, v.π)
    print v

22.3. Depth-first search

깊이 우선 탐색에서는 가장 최근에 탐색된 정점으로부터 탐색되지 않은 정점을 탐색해 나간다. 해당 정점의 모든 간선이 탐색되었으면 그 탐색은 후진하여 그 정점을 발견한 정점의 다른 간선을 탐색한다. 이는 시작점으로부터 도달 가능한 모든 정점을 탐색할 때까지 계속된다. 넓이 우선 탐색과 비슷하게 v의 전임자를 v.π로 마킹한다. 똑같이 전임 부분그래프를 만들 때 형성되는 그래프는 깊이 우선 숲으로 여러 개의 깊이 우선 트리로 이루어진다. 이를 구성하는 간선은 역시 트리 간선이다. 모든 정점은 최초에 흰색이며 이것이 간선 탐색에 의해 발견될 때 회색이 되고 완료될 때 검은색이 된다. 발견된 시점완료된 시점 각각에 대한 타임스태프도 찍힌다. 구현은 다음과 같다.

DFS(G)
for each vertex u ∈ G.V
    u.color = WHITE
    u.π = NIL
time = 0
for each vertex u ∈ G.V
    if u.color == WHITE
        DFS-VISIT(G, u)
DFS-VISIT(G, u)
time += 1
u.d = time
u.color = GRAY
for each v ∈ G.Adj[u]
    if v.color == WHITE
        v.π = u
        DFS-VISIT(G, v)
u.color = BLACK
time += 1
u.f = time

수행 시간은 \Theta(V + E)이다.

Properties of depth-first search

깊이 우선 탐색의 발견 시점과 완료 시점은 괄호 구조를 갖는다.

Theorem. 그래프 G = (V, E)에 대한 깊이 우선 탐색의 임의의 두 정점 u, v에 대해 다음 셋 중 하나가 성립한다.

  • 구간 [u.d, u.f]과 [v.d, v.f]는 서로소이며 깊이 우선 숲 내에서 u나 v는 서로의 조상이 아니다.
  • 구간 [u.d, u.f]는 [v.d, v.f]에 포함되며 깊이 우선 숲 내에서 u는 v의 조상이다.
  • 구간 [v.d, v.f]는 [u.d, u.f]에 포함되며 깊이 우선 숲 내에서 v는 u의 조상이다.

Corollary. 깊이 우선 숲 내에서 v가 u의 조상일 조건은 u.d < v.d < v.f < u.f일 조건과 동치이다.

Theorem. 그래프 G = (V, E) 내의 깊이 우선 숲 내에서 v가 u의 조상일 조건은 u.d 시점에서 u에서 v로의 전부 흰색 정점으로만 이루어진 경로가 존재할 조건과 동치이다.

Classification of edges

깊이 우선 숲에서 간선들은 4가지로 분류될 수 있다.

  1. 트리 간선. (u, v) 탐색 중 v가 최초로 발견된 경우.
  2. 후방 간선. u에서 조상 v로의 간선. 자가 순환은 후방 간선으로 간주한다.
  3. 전방 간선. u에서 후손 v로의 간선인데 트리 간선이 아닌 경우.
  4. 교차 간선. 나머지 전부.

(u, v)에서 v의 색이 흰색이면 트리 간선, 회색이면 후방 간선, 검은색이면 전방 간선 또는 교차 간선이다.

Theorem. 비방향그래프 G의 깊이 우선 탐색에 대해 모든 간선은 트리 간선이거나 후방 간선이다.

22.4. Topological sort

방향 비순환 그래프 G = (V, E)에서의 위상 정렬은 정점들에 대한 선형 순서로서 간선 (u, v)가 존재하는 경우 u가 v 앞에 오는 순서이다. 구현은 다음과 같다.

TOPOLOGICAL-SORT(G)
call DFS(G) to compute finishing times v.f for each vertex v
as each vertex is finished, insert it onto the front of a linked list
return the linked list of vertices

수행 시간은 \Theta(V + E)이다.

Lemma. 방향그래프 G에 순환이 없을 조건은 깊이 우선 탐색에서 후방 간선이 없을 조건과 동치이다.

Theorem. TOPOLOGICAL-SORT는 방향 비순환 그래프에 대한 위상 정렬을 수행한다.

22.5. Strongly connected components

깊이 우선 탐색의 적용례로 방향 그래프를 강연결요소들로 분해하는 것이 있다.

STRONGLY-CONNECTED-COMPONENT(G)
call DFS(G) to compute finishing times u.f for each vertex u
compute G.T
call DFS(G.T), but in main loop of DFS, consider the vertices in order of decreasing u.f
output the vertices of each tree in the depth-first forest formed in line 3 as a separate strongly connected component

이는 연결 요소 그래프의 성질과 관련이 있다.

Lemma. C, C’가 방향그래프 내 서로 다른 강연결요소일 때 u, v가 C 내의 정점이고 u’, v’가 C’ 내의 정점이면 그래프 내에 u에서 u’로의 경로가 있으면 v’에서 v로의 경로는 있을 수 없다.

Lemma. C, C’가 방향그래프 내 서로 다른 강연결요소일 때 C 내의 정점 u에서 C’ 내의 정점 v로의 간선이 존재한다면 C의 정점들이 발견된 마지막 시간은 C’의 정점들이 발견된 마지막 시간보다 늦다.

Corollary. C, C’가 방향그래프 내 서로 다른 강연결요소일 때 C 내의 정점 u가 C’ 내의 정점 v로부터의 간선이 존재한다면 C의 정점들이 발견된 마지막 시간은 C’의 정점들이 발견된 마지막 시간보다 빠르다.

Theorem. STRONGLY-CONNECTED-COMPONENT는 방향그래프 G의 강연결요소들을 계산한다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중