22.1 Representations of graphs
22.2 Breadth-first search
22.3 Depth-first search
22.4 Topological sort
22.5 Strongly connected components
22 기본 그래프 알고리즘
이번 챕터는 그래프를 나타내고, 그래프를 search하는 방법들을 보여준다. graph를 search한다는 것은 그래프의 정점들을 방문하기 위해서 체계적으로 그래프의 엣지들을 따라가는 것을 의미한다. graph-searching algorithm은 한 그래프의 구조에 대해 많은 것을 발견할 수 있다. 많은 알고리즘은 그들의 구조적 정보를 얻기위해 그것들의 input graph를 찾음으로써 시작한다. 몇 가지 다른 그래프 알고리즘은 기본 그래프 서칭에 공들인다. 그래프를 서칭하는 기법들은 그래프 알고리즘 분야의 중심부에 놓여있다.
Section 22.1은 그래프의 두 가지 가장 흔한 컴퓨터 표기를 다룬다: 인접리스트와 인접행렬로서. Section 22.2는 breadth-first search라고 불리는 간단한 그래프 서칭 알고리즘을 보여주고, 어떻게 breadth-first tree를 만드는지를 보여준다. Section 22.3은 depth-first search를 다루고 depth-first search가 정점을 방문하는 순서에 대한 표준적인 결과를 증명한다. Section 22.4는 depth-first search의 첫 번째 실제 적용을 제공한다: directed acyclic graph(방향이 있는 비순환 그래프)를 위상적으로 정렬하는 것. 방향이 있는 그래프의 강하게 연결된 성분을 발견하는 depth-first search의 두 번째 적용은 Section 22.5의 주제이다.
22.1 Representations of graphs
우리는 한 그래프 G = (V,E)를 나타내는 두 가지 표준적인 방법중에 선택할 수 있다: 인접 리스트의 모음 또는 인접행렬. 두 방법은 모두 방향이 있고 방향이 없는 그래프에 적용된다. 인접-리스트 표현은 sparse graphs를 나타내는 compat 방식을 제공하기 때문에, - |E|는 |V|^2보다 작은 것들이다 - 그것은 보통 선택의 방식이다. 이 책에서 나타내지는 대부분의 그래프 알고리즘은 input graph가 인접 리스트 형태로 나타내진다고 가정된다. 그러나, 우리는 인접행렬의 표현을 선호할지도 모른다, 그래프가 dense일 때 - |E|가 |V|^2에 가깝다 - 또는 우리가 빠르게 두 개의 주어진 정점에 연결하는 한 엣지가 있는지를 구분할 필요가 있을 때. 예를들어, Chapter 25에서 모든 쌍들의 가장 짧은 경로 알고리즘은 그것들의 input graphs가 인접행렬로 나타내진다고 가정한다.
한 그래프 G = (V,E)의 인접-리스트 표현은 |V|개의 리스트의 배열 Adj로 구성된다. V에서 각 정점에 대해 하나씩. V에 있는 각각의 u에 대해, 인접 리스트 Adj[u]는 E에 있는 edge(u,v)가 있게하는 모든 정점 v를 포함한다. 즉, Adj[u]는 G에서 u에 인접한 모든 정점들로 구성된다. (대안적으로, 그것은 이러한 정점들의 포인터들을 포함할지도 모른다.) 인접리스트는 한 그래프의 엣지들을 나타내기 때문에, 슈도코드로 우리는 그 Adj 배열을 그래프의 한 속성으로서 다룬다. 우리가 edge set E를 다루는 것 처럼. 슈도코드에서, 그러므로, 우리는 G.Adj[u]와 같은 표기법을 볼 것이다. 그림 22.1(b)는 그림 22.1(a)의 방향이 없는 그래프의 인접리스트 표현이다. 유사하게, 그림 22.2(b)는 그림 22.2(a)에서 방향이 있는 그래프의 인접리스트 표현이다.
만약 G가 방향이 있는 그래프라면, 모든 인접리스트의 길이의 합은 |E|이다. 왜냐하면 (u,v) 형태의 한 edge는 v가 Adj[u]에 나타나도록 하여 표기되기 때문이다. 만약 G가 방향이 없는 그래프라면, 모든 인접 리스트의 길이의 합은 2|E|이다. 왜냐하면 만약 (u,v)가 방향이 없는 edge라면, 그러면 u는 v의 인접리스트에서 나타나고 그 역도 성립하기 때문이다. 방향이 있는 그래프와 없는 그래프 둘다 에게, 인접리스트 표현은 그것이 요구하는 메모리의 양이 Ө(V + E)이다.
우리는 쉽게 가중치 그래프를 표현하는데 인접리스트를 적용할 수 있다. 즉, 각 edge가 사상된 weight를 가지고, weight function w : E -> R(real) 이 일반적으로 주어진 그래프를 말한다. 예를들어, G = (V,E)가 가중치 함수 w가 있는 가중치 그래프라고 하자. 우리는 간단히, u의 인접리스트에 있는 정점 v로 E에 있는 edge (u,v)의 가중치 w(u,v)를 저장한다. 그 인접리스트 표현은 우리가 많은 다른 그래프 변형을 지원하도록 수정할 수 있다는 점에서 꽤 튼튼하다.
인접리스트 표현의 잠재적인 불이익은 그것이 주어진 edge (u,v)가 그래프에 존재하는지 찾기 위해, 인접리스트 Adj[u]에서 v를 찾는 것 말고는 더 빠른 방법을 제공하지 않는 다는 것이다. 그 그래프의 인접 행렬 표기는 이 불이익을 고치지만, asymptotically 좀 더 많은 메모리의 사용의 비용이 있다. (더 빠른 edge lookup을 가능하게 하는 인접리스트의 변형의 제안을 위해 Exercise 22.1.8을 보아라.)
한 그래프 G = (V,E)의 인접 행렬 표기에 대해, 우리는 임의의 방식으로 그 정점들이 1,2, ..., |V| 로 번호를 부여 받는다고 가정한다. 그러고나서 한 그래프 G의 인접행렬 표기는 }V} x |V| 행렬로 구성된다. A = (aij)이고
aij = 1 if(i,j) in E
0 otherwise.
그림 22.1(c)와 22.2(c)는 각각 그림 22.1(a)와 22.2(a)에서의 방향이 없는 그래프와 있는 그래프의 인접행렬이다. 한 그래프의 인접 행렬은 Ө(V^2)의 메모리를 요구한다. 이것은 그래프에서 edges의 개수와 독립적이다..
그림 22.1(c) 에서 인접행렬의 주 대각선의 대칭성을 관찰해라. 방향이 없는 그래프에서 (u,v)와 (v,u)는 같은 edge를 나타내기 때문에, 방향이 없는 그래프의 인접행렬 A는 그것 자신의 전치행렬이다 : A = A^t. 몇몇 프로그램에서 인접행렬의 대각선위에 있는 엔트리들만을 저장하는 것은 수지타산이 맞다. 그리고 거기에서 그래프를 저장하기 위해 필요한 메모리를 거의 절반이 된다.
한 그래프의 인접 리스트 표기처럼, 인접 행렬은 가중치 있는 그래프를 나타낼 수 있다. 예를들어, G = (V,E)가 edge-weight function w가 있는 가중치 있는 그래프라면, 우리는 간단히 E에 있는 edge (u,v)의 가중치 w(u,v)를 인접 행렬의 행 u와 열 v에 있는 entry로서 저장할 수 있다. 만약 한 edge가 존재하지 않는다면, 우리는 그것의 대응되는 매트릭스 entry에 NIL value를 저장할 수 있다. 비록 대부분에 문제들에 대해 0 또는 무한대같은 값을 사용하는 것이 편리할지라도.
비록 인전행렬 표기가 인접행렬 표기만큼 적어도 공간 효율적일지라도, 인접 행렬은 더 간다하고, 그래서 우리는 그래프가 합리적으로 작을 때 그것들을 선호할지도 모른다. 게다가,
인접행렬은 가중치 없는 그래프에 대해 더 이득을 지닌다: 그들은 entry당 1비트만을 요구한다.
Representing attributes
그래프에서 작동하는 대부분의 알고리즘은 정점 그리고/또는 edges에 대한 특성을 유지할 필요가 있따. 우리는 우리 자신의 표기법인 정점 v의 특성 d에 대해 v.d같은 것을 사용하여 이러한 특성을 나타낸다. 예를들어, edges가 attribute f를 가진다면, 우리는 이러한 edge (u,v)에 대한 특성을 (u,v).f로 표기한다. 알고리즘을 보여주고 이해하는 목적으로, 우리의 attribute notation은 충분하다.
실제 프로그램에서 vertex와 edge attributes를 구현하는 것은 전적으로 다른 이야기가 될 수 있따. vertex와 edge attributes를 저장하고 접근하는 가장 좋은 것이 아니다. 주어진 상황에 대해서, 너의 결정은 너가 사용하고 있는 프로그래밍 언어, 너가 구현하려는 알고리즘, 그리고 너의 프로그램의 나머지가 어떻게 그래프를 사용하는지에 달려있다. 만약 너가 인접 리스트를 사요하여 그래프를 나타낸다면, 한 디자인은 additional arrays에서 vertex attributes를 나타낸다. Adj arra와 평행한 array d[1..|V|} 같은. 만약 u에 인접한 정점들이 Adj[u]에 있다면, 그러면 우리가 그 attribute u.d를 부르는것은 실제로 array entry d[u]에 저장되어 있을 것이다. 특성을 구현하는 많은 다른 방법들은 가능하다. 예를들어, 객체지향 프로그래밍 언어에서, vertex attributes는 Vertex class의 하위클래스 내의 instance variables로 나타내어질 지도 모른다.
22.2 Breadth-first search
BFS는 그래프를 서치하는 가장 간단한 알고리즘 중의 하나이고, 많은 중욯ㄴ 그래프 알고리즘의 원형이다. 프림의 최소신장트리 알고리즘 (Section 23.2)과 다익스트라의 single-source shortest-paths algorithm(Section 24.3)은 BFS에서의 것들과 유사한 아이디어들을 사용한다.
그래프 G = (V,E)와 구분되는 source vertex s가 주어진다면, BFS는 체계적으로 s로 부터 도달가능한 모든 정점을 "발견"하기 위해서 G의 edges를 탐험한다. 그것은 s에서 각 도달가능한 정점 거리(edges의 가장 작은 개수)를 계산한다. s에서 도달가능한 어떤 정점 v에 대해, s에서 v로 가는 BFS tree에서 간단한 경로는 그래프 G에서 s에서 v로 가는 가장 짧은 경로와 일치한다. 즉, 가장 적은 수의 edges를 포함하는 경로이다. 그 알고리즘은 방향 있는 그래프, 방향 없는그래프 둘 다에 작동한다.
BFS는 그것이 발견된 정점과 발견되지 않은 정점 사이의 frontier를 frontier의 너비를 넘어서 넓히기 때문에 그렇게 이름지어 진다. 즉, 그 알고리즘은 k + 1의 거리에 있는 어떤 정점을 발견하기 전에, s에서 거리 k에 있는 모든 정점을 발견한다.
나아가는 것을 추적하기 위해, bfs는 각 vertex를 white, gray, or black으로 칠한다. 모든 정점은 white로 시작하고, 나중에 gray 그러고나서 black이 된다. 한 vertex는 search 동안에 만난 처음에 discovered 된다. 그리고 그 때, 그것은 nonwhite이다. 그러므로 Gray and black 정점은 발견되어진 것이지만, BFS는 그것들 사이를 그 search가 breadth-fisrt 방식으로 나아가도록 하기위해 구분한다. 만약 E에 있는 (u,v)와 정점 u가 black이라면, 그러면 v는 gray or black이다; 즉, black 정점들에 인접한 모든 정점들이 발견된다. Gray vertices는 인접한 white vertices를 가질지도 모른다; 그것들은 발견된 정점과 발견되지 않은 정점 사이의 국경을 나타낸다.
BFS는 Breadth-first tree를 구성한다. 이것은 초기에 오직 그것의 root만을 포함한다. root는 source vertex s이다. 그 search가 이미 발견된 vertex u의 인접 리스트를 탐색하는 과정에서 white vertex v가 발견될 때 마다, 그 정점 v와 edge(u,v)는 트리에 더해진다. 우리는 u가 breadth-first tree에서 v의 predecessor 또는 v의 부모라고 말한다. 한 vertex가 최대 한 번씩 발견되기 때문에, 그것은 많아봐야 하나의 부모를 가진다. BF-tree에서 조상과 후손의 관계는 보통 root s와 상대적으로 정의된다: 만약 u가 root s에서 vertex v로 가는 tree의 간단한 경로에 있다면, u는 v의 조상이고 v는 u의 후손이 된다.
breadth-first-search 절차 BFS는 아래에서, input graph G = (V,E)가 인접리스트를 사용하여 표기된다고 가정한다. 그것은 그래프에서 각 정점에 대한 몇 가지 추가적인 attributes를 더한다. 우리는 attribute u.color에 V에 있는 vertex u의color를 저장하고, attribute u.pi에 u의 predecessor를 저장한다. 만약 u가 predecessor가 없다면 (예를들어, u = s이거나 u가 발견되지 않았다면), 그러면 u.pi = NIL 이다. attribute u.d는 source s에서 vertex u까지 알고리즘으로 계산된 거리를 지닌다. 그 알고리즘은 또한 first-in, first-out queue Q (see Section 10.1)을 사용한다. gray vertices의 집합을 관리하기 위해서.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | for each vertex u in G.V - {s} u.color = WHITE u.d = infinity u.pi = NIL s.color = GRAY s.d = 0 s.pi = NIL Q = 0 ENQUEUE(Q, s) while Q != 0 u = DEQUEUE(Q) for each v in G.adj[u] if v.color == WHITE v.color = GRAY v.d = u.d + 1 v.pi = u ENQUEUE(Q,v) u.color = BLACCK |
그림 22.3은 sample graph에서 BFS의 진척을 보여준다.
BFS 절차는 다음과 같이 작동한다. source vertex s의 예외와 함께, line 1-4는 모든 vertex white로 칠하고, u.d를 각 vertex u에 대해 무한대로 설정하고, 모든 정점의 부모를 NIL로 설정한다. Line 5는 s를 gray로 칠한다. 우리는그것이 절차가 시작될 때 발견되는 것으로 고려하기 때문이다. Line 6은 s.d를 0으로 초기화하고, line 7은 그 source의 predecessor를 NIL로 설정한다. LIne 8-9는 Q가 vertex s만을 포함하는 큐로 초기화한다.
lines 10-18의 while loop는 회색의 정점들이 남아있는 한 반복한다. 그리고 그 회색 정점들은 완전히 검사되지 않은 인접리스트를 가진 발견된 정점들이다. while loop는 다음의 불변자를 유지한다:
line 10에서의 검증에서, 큐 Q는 회색 정점의 집합으로 구성된다.
비록 우리가 옳음을증명하기 위해 이 loop invariant를 사용하지 않을 것이지만,그것은 first iteration 전에 유효하고, 그 loop의 매 반복이 그 invariant를 유지한다는 것을 보는 것은 쉽다. 첫 번째 반복 전에, 유일한 gray vertex, 그리고 큐에 있는 유일한 vertex는 source vertex s이다. Line 11은 queue Q의 머리에 있는 gray vertex u를 결정한다. 그리고 그것을 Q로부터 제거한다. lines 12-17의 for loop는 u의 인접리스트의 각 정점 v를 고려한다. 만약 v가 white라면, 그러면 그것은 아직 발견되지 않았고, 그 절차는 lines 14-17을 실행하여 그것을 발견한다. 그 절차는 vertex v gray를 칠하고, 그것의 거리를 v.d를 u.d + 1로 설정하고, u를 그것의 부모 v.pi로서 설정한다. 그리고 그것을 queue Q의 tail에 둔다. 일단 그 절차가 u의 인접리스트에 있는 모든 정점을 검사했다면, 그것은 line 18에 있는 u를 검은색으로 만든다. 한 vertex가 회색으로 칠해질 때 마다 (line 14) 그것이또한 큐에 들어가기 때문에 (line 17), 그리고 한 vertex가 dequeued 될 때 마다 (line 11) 그것은 또한 검은색으로 칠해지기 때문에 (line 18) loop invariant가 유지된다.
BFS의 결과는 한주어진 정점의 이웃들이 LINE 12에서 방문된순서에 의존한다: BF-tree는 다양할지도 모르지만, 알고리즘에의해 계산되는 거리 d는 그렇지 않을 것이다. (see Exercise 22.2-5)
Analysis
BFS의 다양한 특성을 증명하ㅣ 전에, 우리는 input 그래프 G = (V,E)에서 그것의 러닝 타임을 분석하는 어느정도 쉬운작업에 착수한다. 우리는 aggregate 분석을사용한다. 우리가 Section 17.1에서 보았듯이. 초기화 후에, BFS는 결코 한 정점을 하얗게 하지 않고, 따라서 line 13에 있는 그 테스트는 각 정점이 많아봐야 한 번 큐에 들어가게 하고, 그러므로 많아봐야 한 번 큐에서 나오게 된다. enque와 dequeue의 연산은 O(1)의 시간이 걸리고, 그래서 큐 연산에 걸리는 총 시간은 O(V)이다. 절차는 오직 vertex가 dequeued될 때만, 각 정점의 인접리스트를 조사하기 때문에, 그것은 많아봐야 한번 각 인접리스트를 조사한다. 모든 인접리스트의 길이의 합은 Ө(E)이고, 인접리스트를 조사하는데 걸리는 총 시간은 O(E)이다. 초기화를 위한 overhead는 O(V)이고, 그래서 BFS 절차의 최종 러닝 타임은 O(V + E)이다. 따라서, BFS는 G의 인접리스트 표기의 크기에서 선형 시간에 작동한다.
Shortest paths
이 섹션의 초기에, 우리는 BFS가 V에 있는 source vertex s가 주어진 graph G = (V,E)에서 각각의 도달 가능한 vertex의 거리를 찾는다고 주장했었다. s에서 v로 가는 최단경로 거리 &(s,v)를 정점 s에서 정점 v로가는 어떤 경로에서 edges들의 최소 개수라고 정의하자; 만약 s에서 v로 가는 경로가 없다면, &(s,v) = infinity가 된다. 우리는 s에서 v로 가는 &(s,v) 길이의 한 경로를 s에서 v로가는 shortest path로 부른다. BFS가 정확히 최단 경로 거리를 계산한다는 것을 보여주기 전에, 우리는 최단 경로 거리의 중요한 특성을 조사한다.
Lemma 22.1
G = (V,E)가 방향이 있는 또는 방향이 없는 그래프라고 하고, V에 있는 s가 임의의 정점이라고 하자. 그러고나서 E에 있는 어떤 edge(u,v)에 대해
&(s,v) <= &(s,u) + 1 이다.
Proof 만약 u가 s로부터 도달 가능하다면, 그러면 v는 그렇게 된다. 이러한 경우에, s에서 v로 가는 최단 경로는 edge(u,v)가 그 다음에 나오는 s에서 u까지의 최단 경로보다 더 길 수 없다. 따라서 부등식은 유효하다. 만약 u가 s에서 다울 수 없다면, &(s,u) = infinity, 이고, 그리고 부등식은 유효하다.
우리는 BFS가 적절히 V에 있는 각각의 정점 v에 대해, v.d = &(s,v)인 것을 계산하는 것을 보여주고 싶다. 우리는 처음에, v.d를 위에서부터 &(s,v)로 제한하는것을 보여준다.
Lemma 22.2
G = (V,E)가 방향이 있는 또는 없는 그래프라고 하고, BFS가 V에 있는 한 주어진 정점 s로부터 G에서 작동한다고 가정하자. 그런 후에, 종료시에 V에 있는 각 정점 v에 대해, BFS로 연산된 v.d의 값은 v.d >= &(s,v)를 만족시킨다.
Proof 우리는 ENQUEUE 연산의 개수로 귀납법을 사용한다. 우리의 귀납 가설은 V에 있는 모든 v에 대해서 v.d >= &(s,v)라는 것이다.
귀납의 기반은 BFS의 line 9에서 s를 enqueue 한 직후의 상황이다. 귀납 가설은 여기에서 유효하다. 왜냐하면 s.d = 0 = &(s,s)이고, V - {s}에서의 모든 v에 대해
v.d = infinity >= &(s,v) 이기 때문이다.
귀납 단계를 위해, 정점 u로부터 search동안 발견된 white 정점 v를 고려하자. 그 귀납 가설은 u.d >= &(s,u)인 것을 암시한다. line 15에 의해 수행되는 할당으로부터, 그리고 Lemma 22.1으로부터 우리는 다음을 얻는다.
v.d = u.d + 1
>= &(s,u) + 1
>= &(s,v)
Vertex v는 그러고나서 enqueued되고, 그것은 결코 또 다시 enqueued 되지 않는다. 왜냐하면 그것은 또한 grayed되고, 그러고나서 line14-17이 white vertices에 대해서만 실행되기 때문이다. 따라서, v.d의 값은 결코 다시 변하지 않고, 귀납 가설은 유지된다.
v.d = &(s,v)를 증명하기 위해, 우리는 처음에 queue Q가 어떻게 BFS 과정 동안 연산하는지를 보여줘야만 한다. 다음 lemma는 항상, 그 큐가 많아봐야 두 개의 다른 d 값을 가지는 것을 보여준다.
Lemma 22.3
한 그래프 G = (V,E)에서 BFS를 실행하는 동안, queue Q가 (v1, .. vr)의 정점들을 포함한다고 ㄱ자ㅓㅇ하자. 여기에서 v1은 Q의 head이고, vr은 tail이다. 그러면, vr.d <= v1.d + 1 이고 i = 1,2,..., r-1인 것에 대해 vi.d + <= v_(i+1).d 이다.
Proof 증명은 큐 연산의 숫자에 대한 귀납으로 된다. 초기에, 큐가 오직 s만을 포함할 때, 그 lemma는 확실히 유효하다.
inductive step에 대해, 우리는 한 정점을 빼고, 넣고 한 후에도 유효하다는 것을 증명해야 한다. 만약 큐의 헤드 v1이 dequeued 된다면, v2가 새로운 head가 된다. (만약 큐가 비어있다면, 그러면 그 lemma는 무의미하게 유효하다.) 귀납 가설에 의해, v1.d <= v2.d이다. 그러나 그러고나서 우리는 vr.d <= v1.d + 1 <= v2.d + 1을 가지게 되고, 나머지 부등식은 영향 받지 않는다. 따라서, 그 lemma는 v2가 head일 때 따른다.
한 정점을 넣으려고 할 때 발생하는 것을 이해하기 위해서, 우리는 그 코드를 좀 더 세밀하게 조사해야할 필요가 있다. 우리는 BFS의 line 17에서 한 정점 v를 넣으려고 할 때, 그것은 v_(r+1)이 된다. 그 당시에, 우리는 vertex u를 이미 제거했고, 그 정점의 인접리스트는 현재 조사중에 있다. 그 큐 Q로부터, 그리고 귀납 가설에 의해서 새로운 head v1은 v1.d >= u.d를 갖게 된다. 따라서, v_(r+1).d = v.d = u.d + 1 <= v1.d + 1. 귀납 가설로 부터 우리는 또한 v_r.d <= u.d + 1을 가지게 되고, 그래서, vr.d <= u.d + 1 = v.d = v_(r+1).d이게 디ㅗㄴ다. 나머지 부등식은 영향 받지 않는다. 따라서, v가 enque되었을 떄 그 lemma가 따라온다.
다음 corollary는 정점이 넣어질 때 d값이 시간에 따라서 단조 증가하는 것을 보여준다.
Corollary 22.4
정점 v_i와 v_j가 BFS 실행동안 넣어졌다고 가정하고, v_i가 v_j 전에 넣어졌다고 하자. 그러면 v_j가 넣어질 때 v_i.d <= v_j.d 이게 된다.
Proof Lemma 22.3으로부터 즉시, 각 정점이 BFS 동안에 최대 한 번 유한한 D 값을 받는 다는 특성이다.
우리는 BFS가 정확히 최단-경로 거리를 찾는다고 증명할 수 있다.
Theorem 22.5 (Correctness of breadth-first search)
G = (V,E)가 방향이 있는 또는 없는 그래프라고 하고, BFS가 V에 있는 한 주어진 정점 s로부터 G에서 작동한다고 가정하자. 그러면, 그 실행 동안에, BFS는 source s에서 도달할 수 있는 V에 있는 모든 정점 v를 발견하고, 종료시에, V에 있는 모든 v에 대해 v.d = &(s,v)가 된다. 게다가, s로부터 도달 가능한 v != s인 정점에 대해, s에서 v로 가는 가장 짧은 경로 중의 하나는 (v.pi, v) edge가 다음에 나오는 s에서 v.pi까지의 최단 경로이다.
Proof 모순의 목적을 위해, 어떤 정점이 그것의 최단-경로 거리와 같지 않은 값 d를 받았다고 가정하자. v는 그러한 부정확한 d 값을 받은 최소 &(s,v)인 정점이라고 하자; 확실히 v != s이다. Lemma 22.2에 의해, v.d >= &(s,v)이고, 따라서 우리는 v.d > &(S,v)를 갖는다. 정점 v는 s로부터 닿을 수 있어야 한다, 그렇지 않으면, &(s,v) = infinity >= v.d가 되기 떄문이다. u가 s에서 v로가는 최단 경로에서 v를 바로 선행하는 정점이라고 하자. &(s,v) = &(s,u) + 1이 되도록 하기 위해서. &(s,u) < &(s,v)이기 떄문에, 그리고 우리가 v를 선택한 방법 때문에, 우리는 u.d = &(s,u)를 갖는다. 이러한 특징을 합쳐서, 우리는
v.d > &(s,v) = &(s,u) + 1 = u.d + 1 (22.1)
을 갖는다.
이제 BFS가 line 11에서 Q로부터 정점 u를 빼는 것을 선택할 때를 고려해보자. 이 때, vertex v는 white, gary, or black 중에 하나이다. 우리는 이러한 경우들 각각에 대해, 부등식 (22.1)에 대한 모순을 끌어내는 것을 보여줄 것이다. 만약 v가 white라면, 그러면 line 15는 v.d = u.d + 1로 설정하고, 부등식 (22.1)에 모순된다. 만약 v가 black이라면, 그러면 그것은 이미 queue에서 제거되어졌고, Corollary 22.4에 의해, 우리는 v.d <= u.d를 갖고 이것은 부등식 22.1에 모순된다. v가 gray라면, 그러면 그것은 어떤 정점 w를 뺄 때 gray로 칠해지고, 그 w는 u보다 일찍 Q에서 제거된다. 왜냐하면 v.d = w.d + 1이기 때문이다. Corollary 22.4에 의해, 그러나 w.d <= u.d이고 그래서 우리는 v.d = w.d + 1 <= u.d + 1을 가즌ㄴ다. 그리고 이것은 다시 부등식에 모순이다.
따라서 우리는 V에 있는 모든 정점 v에 대해 v.d = &(s,v)라고 결론짓는다. s로부터 도달 가능한 모든 정점 v는 발견되어져야만 하고, 그렇지 않으면 그것들은 infinity = v.d > &(s,v)이기 때문이다. 그 정리의 증명을 결론짓기 위해서, 만약 v.pi = u라면, v.d = u.d + 1라는 것을 관찰해라. 따라서, 우리는 s에서 v.pi로 가능 최단 경로를 취하여 s에서 v로가는 최단 경로를 얻을 수 있다. 그러고나서 edge(v.pi, v)를 가로지른다.
Breadth-first trees
BFS 절차는 그것이 그래프를 search할 때, BF-tree를 구성한다. 그림 22.3이 보여주듯이, 그 트리는 pi attributes와 대응된다. 좀 더 공식적으로, source s가 있는 한 그래프 G = (V,E)에 대해, 우리는 G의 predecessor subgraph를 G_pi = (V_pi, E_pi)로 정의하고, 거기에서
V_pi = {v in V : v.pi != NIL} U {s}
그리고
E_pi = {(v.pi,v): v in V_pi - {s}}.
predecessor subgraph G_pi는 만약 V_pi가 s로부터 도달할 수 있는 정점들로 구성된다면 breadth-first tree이다. 그리고 V_pi에 있는 모든 v에 대해, 그 subgraph G_pi는 s에서 v로 가는 unique simple path를 포함하고, 이것은 또한 G에서 s에서 v로 가는 최단 경로이다. breadth-first tree는 사실 한 트리이다. 왜냐하면 그것은 연결되어있고, |E_pi| = |V_pi| - 1이기 떄문이다. (정리 B.2를 보아라.) 우리는 E_pi에 있는 edges들을 tree edges라고 부른다.
다음 lemma는 BFS 절차에 의해 만들어진 predecessor subgraph가 BF-tree라는 것을 보여준다.
Lemma 22.6
방향이 있는 또는 없는 그래프 G = (V,E)에 적용될 때, BFS 절차는 predecessor subgraph G_pi = (V_pi, E_pi)가 BF-tree가 되도록 하는 pi를 구성한다.
Proof BFS의 Line 16은 v.pi = u을 설정한다. <=> E에 있는 (u,v)이고, &(s,v) < infinity이다. - 즉, v가 s로부터 도달 가능한다면 - 그리고 따라서 V_pi는 s에서 도달가능한 V에 있는 정점들로 구성된다. G_pi가 tree를 형성하기 때문에, B.2 정리에 의해, 그것은 s에서 V_pi에 있는 각 vertex로 가는 unique simple path를 포함한다. 정리 22.5를 귀납적으로 적용하여, 우리는 모든 그러한 경로가 G에서 최단 경로라는 것을 결론 짓는다.
다음 절차는 s에서 v로가는 최단 경로의 정점들을 출력한다. 이것은 BFS가 이미 BF-tree를 연산했다는 것을 가정한다.
PRINT_PATH(G, s, v) 1 if v == s 2 print s 3 else if v.pi == NIL 4 print "no path from" s "to" v "exists" 5 else PRINT-PATH(G, s, v.pi) 6 print v
이 절차는 print된 경로에서 정점의 수만큼 선형 시간으로 작동한다. 각 재귀 호출은 한 경로에 대해 더욱 짧아지기 때문이다.
22.3 Depth-first search
depth-first search의 전략은, 그것의 이름이 암시하듯이, 가능할 때 마다 그래프를 좀 더 깊게 search하는 것이다. DFS는 가장 최근에 발견된 vertex v에서 edges들을 탐험한다. 그리고 그 v는 여전히 그것을 떠나는 탐사되지 않은 edges들을 가지고 있다. 모든 v의 edges들이 탐험되어졌다면, 그 search는 "backtracks"을 한다. v가 발견되었던 vertex를 떠나는 edges들을 탐험하기 위해서. 이 과정은 우리가 원래의 source vertex로부터 도달가능한 모든 정점을 발견할 때 까지 계속 된다. 만약 어떤 발견되지 않은 정점들이 남아있다면, 그러면 DFS는 그것들 중 하나를 새로운 source로 선택하고, 그 소스로부터 그 search를 반복한다. 그 알고리즘은 그것이 모든 정점을 발견할 때 까지 전체 프로세스를 반복한다.
BFS에서 처럼, DFS가 이미 발견된 vertex u의 인접 리스트의 scan동안에 vertex v를 발견할 때 마다, 그것은 v의 predecessor attribute v.pi를 u로 설정하여 이 사건을 기록한다. predecessor subgraph가 트리를 형성하는 BFS와 다르게, DFS에 의해 만들어지는 predecessor subgraph는 몇 가지 트리들로 구성될지도 모른다. 왜냐하면 그 탐색은 다양한 sources로부터 반복할지도 모르기 때문이다. 그러므로, 우리는 DFS의 predecessor subgraph를 BFS의 그것과 다르게 정의한다: 우리는 G_pi = (V, E_pi)라고 하고, 여기에서
E_pi = {(v.pi, v) : v in V and v.pi != NIL} 이다.
DFS의 predecessor subgraph는 depth-first forest를 형성한다. 이것은 몇 가지 depth-first trees들로 구성되어 있다. E_pi에 있는 edges들은 tree edgse이다.
BFS에서 처럼, DFS는 그것들의 상태를 가리키기 위해 탐색 동안 정점들을 색칠한다. 각 정점은 처음에 white 이고, 탐색시에 발견되었을 때 회식이 되고, 그것이 끝났을 때 검정색이 된다. 즉, 그것의 인접리스트가 완전히 검사되었을 때. 이 기법은 각 vertex가 정확히 한 개의 depth-first tree에서 끝나게 된다. 이러한 트리들이 분리되도록.
depth-first forest를 만드는 것 외에도, DFS는 또한 각 정점을 timestamps한다. 각 정점 v는 두 가지 timestamps를 가진다: 첫 번째 것은 v가 처음으로 발견되었을 때의 v.d records를 timestamp한다. (그리고 v는 회색이 된다.) 두 번째 것은 그 search가 v의 인접리스트를 검사하는 것을 끝냈을 때 v.f records를 timestamp한다. (그리고 v를 검정색으로 만든다.) 이러한 timestamps들은 그래프의 구조에 대한 중요한 정보를 제공하고, 일반적으로 DFS의 행동에 대해 추론하는데 도움이 된다.
아래의 DFS 절차는 그것이 attribute u.d에서 vertex u를 언제 발견하는지를 기록한다. 그리고 attribute u.f에서 언제 vertex u를 끝내는지를 기록한다. 이러한 timestamps들은 1과 2|V|사이의 정수이다. 왜냐하면 한 번의 발견 이벤트와 한 번의 마무리 이벤트가 있기 때문이다. 그 |V| 정점들 각각에 대해. 모든 정점 u에 대해,
u.d < u.f 이다.
정점 u은 u.d 시간 이전에는 WHITE이고, u.d와 u.f 사이의 시간에는 GRAY이고, 그 이후에는 BLACK이다.
다음의 슈도코드는 기본적인 DFS 알고리즘이다. 그 input graph G는 방향이 없거나 있을 수도 있다. 변수 time은 timestamping을 위해 사용하는 전역 변수이다.
DFS(G) 1 for each vertex u in G.V 2 u.color = WHITE 3 u.pi = NIL 4 time = 0 5 for each vertex u in G.V 6 if u.color == WHITE 7 DFS-VISIT(G,u)
DFS-VISIT(G,u) 1 time = time + 1 // white vertex u has just been discovered 2 u.d = time 3 u.color = GRAY 4 for each v in G.Adj[u] // explore edge(u,v) 5 if v.color == WHITE 6 v.pi = u 7 DFS-VISIT(G,v) 8 u.color = BLACK // blacken u; it is finished 9 time = time + 1 10 u.f = time
그림 22.4는 그림 22.2에서 보여진 그래프의 DFS의 진행을 보여준다.
DFS 절차는 다음과 같이 작동한다. Lines 1-3은 모든 정점을 하얗게 칠하고 그것들의 pi 속성을 NIL로 초기화한다. Line 4는 전역 시간 counter를 리셋한다. LInes 5-7은 V에 있는 각 정점을 차례대로 검사하고, white vertex가 발견되었을 때, DFS-VISIT을 사용하여 그것을 방문한다. DFS-VISIT(G,u)가 line 7에서 호출될 때 마다, vertex u는 depth-first forest에서 새로운 tree의 root가 된다. DFS가 반환할 때, 모든 정점 u는 발견시간 u.d와 마무리 시간 u.f를 할당받는다.
DFS-VISIT(G,u)의 각 호출에서, 정점 u는 초기에 white이다. Line 1은 전역 변수 time을 증가시키고, line 2는 time의 새로운 값을 발견 시간 u.d로 기록하고, line 3는 u를 gray로 칠한다. Lines 4-7은 u에 인접한 각 정점 v를 조사하고, 반복적으로 그것이 white라면 v를 방문한다. Adj[u]에 있는 각 정점 v가 line 4에서 고려되어지기 때문에, 우리는 edge(u,v)가 DFS로 탐험되어진다고 말한다. 마지막으로 u를 떠나는 모든 edge가 탐험되어진 후에, lines 8-10은 u를 black으로 칠하고 time을 증가시켜, u.f의 끝나는 시간을 기록한다.
DFS의 결과들은 DFS의 line 5에서 정점을 검사하는 순서와, DFS-VISIT에서 한 vertex의 이웃을 방문하는 순서에 의존한다는 것에 주목해라. 이러한 다른 방문 순서들은 실제로 문제를 일으키는 경향은 없다. 우리는 보통 어떤 DFS 결과를 효과적으로 사용하기 때문에. 필수적으로 동일한 결과를 가진.
DFS의 작동시간은 무엇인가? DFS의 lines 1-3과 lines 5-7의 루프들은 Ө(V)가 걸린다. DFS-VISIT에 대한 호출을 실행시간을 제외하고. 우리가 BFS에서 했던 것 처럼, 우리는 aggregate analysis를 사용한다. DFS-VISIT 절차는 V에 있는 각 정점 v에 대해 정확히 한 번 호출된다. DFS-VISIT이 불러지는 정점 u는 white여야만하고 DFS-VISIT이 처음 하는 것은 vertex u를 gray로 칠하는 것이기 때문이다. DFS-VISIT(G,v)의 실행동안, lines 4-7의 루프는 |Adj[v]|번 실행한다.
sigma(Adj[v]) from v in V = Ө(E),
DFS-VISIT의 lines 4-7의 실행의 총 비용은 Ө(E)이다. 그러므로 DFS의 작동 시간은 Ө(V+E) 이다.
DFS의 특성
DFS는 한 그래프의 구조에 대한 가치있는 정보를 만들어 낸다. 아마도 DFS의 가장 기본적인 특성은 predecessor subgraph G_pi가 참으로 a forest of trees를 만들어 낸다는 것이다. DFS의 구조가 정확히 DFS-VISIT의 재귀 호출의 구조를 반영하기 때문이다. 즉, u = v.pi 이다 <=> DFS-VISIT(G,v)가 u의 인접 리스트의 탐색 동안에 호출된다. 게다가, 정점 v는 depth-first forest에서 정점 u의 후손이다. <=> v는 u가 gray이인 시간 동안에 발견된다.
DFS의 다른 중요한 특징은 발견과 마무리 시간이 괄호 구조를 가진다는 것이다. 만약 우리가 vertex u의 발견을 왼쪽 괄호 "(u"로 나타내고 그것의 마무리를 오른쪽 괄호 "u)"로 나타낸다면, 그러면 발견과 마무리의 history는 괄호가 적절히 nested되는 의미로 잘 형성된 표현을 만든다. 예를들어, 그림 22.5(a)의 DFS는 그림 22.5(b)에 보여지는 괄호화와 일치한다. 다음의 정리는 그 괄호 구조를 특징짓는 다른 방법을 제공한다.
Theorem 22.7 (Parenthesis theroem)
(방향이 있는 또는 없는) 그래프 G =(V,E)의 어떤 DFS에서 든지, 어떤 정점들 u와 v에 대해, 정확히 다음의 세 조건 중 하나가 유효하다:
- [u.d, u.f]와 [v.d, v.f]의 간격은 전적으로 서로 연결되지 않고, u와 v 둘 다 depth-first forest에서 다른것의 후손이 아니다.
- [u.d, u.f]의 간격은 전적으로 [v.d, v.f]의 간격 내에 포함되고, u는 한 depth-first tree에서 v의 후손이거나,
- [v.d, v.f]의 간격은 전적으로 [u.d, u.f]의 간격 내에 포함되고, v는 한 depth-first tree에서 u의 자손이다.
Proof 우리는 u.d < v.d인 경우에서 시작한다. 우리는 v.d < u.f이거나 아닌 것에 따라 두 가지 부분 경우를 고려한다. 첫 번째 부분 경우는 v.d < u.f일 때 발생한다. 그래서 v는 u가 여전히 gray인 동안에 발견된다. 이것은 v가 u의 후손이라는 것을 암시한다. 게다가 v는 u보다 좀 더 최근에 발견되기 때문에, 그것의 밖으로 나가는 edges들 모두 발견된다. 그리고 v는 끝난다. 그 탐색이 u에 반환되고 u를 끝내기전에. 이러한 경우에 ㅡ그러므로, [v.d, v.f]의 간격은 전적으로 [u.d, u.f]의 간격 내에 포함된다. 다른 부분 경우에서, u.f < v.d이고 부등식 22.2 (u.d <u.f)에 의해, u.d < u.f < v.d < v.f이다; 따라서 [u.d, u.f]와 [v.d, v.f]는 겹치지 않는다. 간격이 disjoint이기 때문에 어떠한 정점도 다른 것이 회색인 동안에 발견이 되지 않고, 어떠한 정점도 다른 것의 후손이 아니다.
v.d < u.d인 경우도 비슷하다. u와 v의 역할이 위의 인자에서 바뀌면서.
Corollary 22.8 (Nesting of descendants' intervals)
정점 v는 (방향이 있는 또는 없는) 그래프 G에 대한 depth-first forest에서의 정점 u의 적절한 후손이다. <=> u.d < v.d <v.f < u.f이다.
Proof 정리 22.7에 의해 즉시 된다.
다음 정리는 depth-first forest에서 한 정점이 다른 것의 후손일 때의 또 다른 중요한 특징을 준다.
Theorem 22.9 (White-path theorem)
(방향이 있거나 또는 없는) 그래프 G = (V,E)의 한 depth-first forest에서, 정점 v는 u의 후손이다. <=> 탐색동안 u를 발견한 u.d의 시간에서 전적으로 하얀색 정점들로 구성된 u에서 v로 가는 한 경로가 있다.
Proof =>: 만약 v = u라면, 그러면 u에서 v로 가는 경로는 그냥 vertex u이고, 이것은 여전히 white이다 우리가 u.d의 값을 설정할 때. 이제, v가 depth-first forest에서 u의 적절한 후손이라고 가정하자 Corollary 22.8에 의해 u.d <v.d이고, 그래서 v는 u.d의 시간에 하얀색이다. v는 u의 후손이기 때문에, depth-first forest에서 u에서 v로 가는 unique simple path에서 모든 정점들은 u.d시간에 모두 하얀색이다.
<=: u.d 시간에 u에서 v로 가는 하얀색 정점들로 된 한 경로가 있다고 가장하자. 그러나 v는 depth-first tree에서 u의 후손이 아니라고 하자. 일반성의 손실 없이, 그 길을 따라 v를 제외한 모든 정점들이 u의 후손이라고 가정하자. (그렇지 않으면, v는 u의 후손이 되지 않는 경로를 따라 v에 대해 가장 가까운 정점이라고 하자.) w를 그 경로에서 v의 predecessor라고 하자. w가 u의 후손이 되게 하기 위해서 (w와 u는 사실 같은 정점 일지도 모른다.) Corollary 22.8에 의해, w.f <= u.f이다. v는 u가 발견되고 나서 발견되기 때문에 w가 마무리되기전에 우리는 u.d < v.d < w.f <= u.f를 갖는다. 정리 22.7은 그리고나서 간격 [v.d, v.f]가 전적으로 [u.d, u.f] 간격 내에 포함된다고 암시한다. Corollary 22.8에 의해 v는 결국 u의 후손이여야 한다.
Classification of edges
DFS의 또 다른 흥미로운 특성은 그 탐색이 input graph G = (V,E)의 edges들을 분류하는데 사용될 수 있다는 것이다. 각 edge의 유형은 한 그래프에 대한 중요한 정보를 제공할 수 있따. 예를들어, 다음 섹션에서, 우리는 이것을 볼 것이다. 방향이 있는 그래프는 비순환이다 <=> DFS가 어떠한 "back" edges를 만들어내지 않는다. (Lemma 22.11)
우리는 G에서 DFS로 만들어진 depth-first forest G_pi의 관점에서 4가지 edge types을 정의할 수 있다:
- Tree edges는 depth-first forest G_pi에 있는 edges들이다. Edge(u,v)는 v가 (u,v)edge를 탐험하여 처음 발견된다면 tree edge이다.
- Back edges는 depth-first tree에서 조상 v에 대한 정점 u를 연결하는 edges(u,v)이다.
- Forward edges는 depth-first tree에서 후손 v에 대한 정점 u를 연결하는 nontree edges(u,v)이다.
- Cross edges는 모든 다른 edges이다. 그것들은 같은 depth-first tree에서 정점들 사이를 갈 수 있다. 한 정점이 다른 것의 조상이 아닌 한에서, 또는 그것들은 다른 depth-first tree들을에 있는 정점 사이를 갈 수 있다.
그림 22.4와 22.5에서, edge labels은 edge types들을 가리킨다. 그림 22.5(c)는 또한 그림 22.5(a)의 그래프를 어떻게 다시그릴지를 보여준다. 모든 트리와 forward edges들이 depth-first tree 아래로 향하도록 하고, 모든 back edges들이 위로 향하도록 하기 위해서. 우리는 이러한 방식으로 어떤 그래프든지 다시 그릴 수 있다.
DFS 알고리즘은 그것이 edges를 만날 때, edges들을 분류할 충분한 정보를 가진다. 주된 아이디어는 우리가 한 edge(u,v)를 방문할 때, vertex v의 컬러는 우리에게 edge에 대한 어떤 것을 말해준다:
- WHITE는 tree edge를 가리킨다.
- GRAY는 back edge를 가리킨다.
- BLACK은 forward 또는 cross edge를 가리킨다.
첫 번째 경우는 그 알고리즘의 명시로부터 즉시 온다. 두 번째 경우에 대해서, gray 정점들이 항상 active DFS-VISIT 호출의 스택에 일치하는 후손들의 linear chain을 형성하는 것을 관찰해라. gray 정점들의 개수는 최근 발견된 정점의 depth-first forest의 깊이보다 하나 더 많다. 탐사는 항상 가장 깊은 gray vertex로부터 진행한다. 그래서 다른 gray vertex에 도달한 한 edge는 조상에 접근한다. 세 번째 경우는 나머지 가능성을 다룬다; Exercise 22.3-5는 너에게 그러한 edge (u,v)가 u.d < v.d이면 forward edge인지, u.d > v.d이면 cross edge인지를 보이라고 요청한다.
방향이 없는 그래프는 우리가 어떻게 edges들을 분류할지에서 애매함을 가질지도 모른다. (u,v)와 (v,u)가 정말 같은 edge이기 때문이다. 그러한 경우에, 우리는 edge를 적용되는 분류 목록에서 첫 번째 유형으로 분류한다. 동일하게 (see Exercise 22.3-6) 우리는 그 탐색 encounter가 만나는 (u,v) 또는 (v,u)인지에 따라 edge를 분류한다.
우리는 이제 forward and cross edges가 결코 방향이 ㅇ벗는 그래프에서 일어나지 않는 것을 보여준다.
Theorem 22.10
방향이 없는 그래프 G의 DFS에서, G의 모든 edge는 tree edge이거나 back edge이다.
Proof (u,v)가 G의 임의의 edge라고 하자, 그리고 일반성의 손실 없이 u.d <v.d라고 가정하자. 그리고나서 그 탐색은 그것이 u를 끝내기전에 (u는 gray이인 동안에) v를 발견하고 끝낼야만 한다. v가 u의 인접리스트이기 때문이다. 만약 그 탐색이 edge (u,v)를 찾는 것이라면, 그것은 u->v로 가는 방향에 있고, 그리고나서 v는 그 시간까지 발견되지 않는다 (white), 왜냐하면 그렇지 않으면 그 탐색은 u->v의 방향에 이미 이 edge를 탐험하기 때문이다. 따라서, (u,v)는 tree edge이다. 만약 그 탐색이 처음에 v->u로 가는 방향으로 (u,v)를 탐색한다면, 그러면 (u,v)는 back edge이다. u는 여전히 edge가 처음에 발견된 때에 gray이 이기 때문이다.
우리는 다음 섹션에서 이러한 정리들의 몇 가지 적용들을 볼 것이다.
22.4 Topological sort
이 섹션은 방향이 있는 비순환 그래프(a directed acyclic graph, 또는 소위 "dag")의 위상정렬을 수행하기 위해 우리가 어떻게 DFS를 사용할 수 있는지를 보여준다. dag G = (V,E)의 위상정렬은 모든 그것의 정점들의 선형 ordering인데, 만약 G가 한 edge(u,v)를 포함한다면, 그러면 u는 순서에서 v이전에 나타난다. (만약 그 그래프가 순환을 포함한다면, 그러면 어떤 선형 ordering도 가능하지 않다.) 우리는 한 그래프의 위상정렬을 모든 방향이 있는 edges들이 왼쪽에서 오른쪽으로 가도록 수평 선을 따라 그것의 정점들의 ordering으로 볼 수 있다. 위상정렬은 따라서 Part 2에서 연구된 "sorting"의 일반적인 종류와는 다르다.
많은 프로그램은 사건들 사이에서 우선을 가리키기위해 방향이 있는 비순환 그래프들을 사용한다. 그림 22.7은 Professor Bumstead가 아침에 옷을 입을 때 발생하는 한 예시를 준다. 그 교수는 다른 것들 전에 어떤 의류들을 입어야 한다. (예를들어, 신발전에 양말). 다른 아이템들은 어떤 순서 든지로 넣어질지도 모른다 (예를들어 양말과 바지) 그림 22.7(a)의 dag에서 방향이 있는 edge (u,v)는 의류 u가 의류 v전에 입어져야만 한다는 것을 가리킨다. 그러므로 이 dag의 위상 정렬은 입혀질 순서를 준다. 그림 22.7(b)는 수평선에 따라 정점들에게 ordering한것으로서 위상적으로 정렬된 dag을 보여준다. 모든 방향이 있는 edges가 왼쪽에서 오른쪽으로 가도록.
다음의 간단한 알고리즘은 dag를 위상적으로 정렬한다:
그림 22.7(b)는 어떻게 위상적으로 정렬된 정점들이 그것들이 끝나는 시간의 역순으로 나타나는 지를 보여준다.
우리는 Ө(V + E) 시간안에 위상정렬을 수행할 수 있다. 왜냐하면 DFS는 Ө(V+E) 시간이 걸리고, |V| 정점 각각을 linked list의 앞에 넣는데 O(1)이 걸리기 때문이다.
우리는 방향이 있는 비순환 그래프를 특징화하는 다음의 주된 lemma를 사용하여 이 알고리즘의 정당성을 증명한다.
Lemma 22.11
방향이 있는 그래프 G는 비순환이다 <=> DFS가 어떤 back edges를 만들어 내지 않는다.
Proof =>: DFS가 back edge (u,v)를 만든다고 가정하자. 그러면 정점 v는 depth-first forest에서 정점 u의 한 조상이다. 따라서, G는 v에서 u로가는 한 경로를 포함하고 그래서 back edge(u,v)는 한 사이클은 완성짓는다.
<=: G가 cycle c를 포함한다고 가정하자. 우리는 G의 DFS가 back edge를 만들어낸다는 것을 보여준다. v가 c에서 발견될 첫 번째 정점이라고 하고, (u,v)가 c에서 선행하는 edge라고 하자. v.d 시간에, c의 정점들은 v에서 u로가는 white vertices에 대한 한 경로를 형성한다. white-path 정리에 의해, 정점 u은 depth-first forest에서 v의 후손이 된다. 그러므로, (u,v)는 back edge이다.
Theorem 22.12
TOPOLOGICAL-SORT는 그것의 입력으로서 제공된 방향이 있는 비순환 그래프의 위상 정렬을 만들어낸다.
Proof DFS가 그것의 정점들에 대한 마무리 시간을 결정하기 위해 주어진 dag G = (V,E)에서 작동한다고 가정하자. V에 있는 별개의 정점의 쌍 u,v에 대해, 만약 G가 u->v의 edge를 포함한다면, 그러면 v.f < u.f라는 것을 보여주는 것은 충분하다. DFS(g)에 의해 탐사되는 어느 edge(u,v)에 대해 고려하자. 이 edge가 탐험되었을 때, v는 gray가 될 수 없다. 왜냐하면 그러고나서 v는 u의 조상이 될것이고 (u,v)의 back edge가 될 것이기 때문이다. 이것은 22.11 Lemma와 모순이 된다. 그러므로 v는 white 또는 black이여야 한다. 만약 v가 white라면, 그것은 u의 후손이되고, 그래서 v.f < u.f가 된다. 만약 v가 black이라면, 그것은 이미 끝나졌다. v.f가 이미 설정되었기 되도록. 우리는 여전히 u로부터 탐사중이기 때문에, 우리는 아직 u.f에 대해 timestamp를 할당해야만 하고, 그래서 우리가 그렇게 한다면, 우리는 v.f < u.f를 또한 갖을 것이다. 따라서, dag에 있는 어떤 edge (u,v)에 대해, 우리는 v.f < u.f 가지고, 정리에 대해 증명한다.
22.5 Strongly connected components
우리는 이제 DFS의 고전적인 적용을 고려한다: 방향이 있는 그래프를 strongly connected components로 분해하기. 이 섹션은 두 개의 DFS를 사용하여 어떻게 그렇게 하는지를 보여준다. 방향이 있는 그래프와 작동하는 많은 알고리즘은 그러한 분해로 시작한다. 그래프를 strongly connected compontes(SCC)로 분해한 후에, 그러한 알고리즘은 각각에 대해 별개로 작동하고, 그러고나서 컴포넌트들의 사이에 있는 연결 구조에 따라서 솔루션들을 합친다.
Appendix B로부터 한 방향이 있는 그래프 G = (V,E)의 하나의 SCC는 V에 포함되는 정점들의 maximal 집합 C라는 것을 상기하라. 이것은 C에 있는 정점들 u,v의 모든 쌍에 대해, 우리가 u -> v와 v ->u를 둘 다 갖게 하기 위해서이다; 즉, 정점 u와 v는 서로에게 접근가능하다. 그림 22.9는 한 예제를 보여준다.
한 그래프 G = (V, E)의 한 SCC를 찾는 우리의 알고리즘은 G의 전치행렬을 사용한다. 그리고 우리는 그 전치행렬은 연습문제 22.1-3에서 G^t = (V, E^t)로 정의했었다. 거기에서
E^t = {(u,v): (v,u) in E} 이다. 즉, E^t는 그들의 방향이 역전된 G의 edges로 구성된다. G의 인접리스트 표기법이 주어진다면, G^t를 만드는 시간은 O(V + E)이다. G와 G^t가 정확히 같은 SCC를 같는 것을 관찰하는 것은 흥미롭다: u와 v는 G에서 서로 접근 가능하다 <=> 그들은 G^t에서 서로 접근가능 하다. 그림 22.9(b)는 그림 22.9(a)에서 그래프의 전치행렬을 보여주고, SCC들이 그림자표시 되어있다.
다음의 선형-시간의 (즉, Ө(V + E) 시간) 알고리즘은 한 방향이 있는 그래프 G = (V,E)의 SCC를 두 개의 DFS를 사용하여 연산한다. 하나는 G에 하나는 G^t에.
이 알고리즘 뒤에 있는 아이디어는 component graph G^SCC = (V^SCC, E^SCC)의 주요 특징으로부터 온다. 우리는 그것을 다음과 같이 정의한다. G가 C_1, C_2, ... , C_K인 SCC를 가진다고 가정하자. 그 정점의 집합 V^SCC는 {v_1, v_2, ..., v_k}이고, 그리고 그것은 G의 각각의 SCC C_i에 대해 정점 v_i를 포함한다. 만약 G가 C_i에 있는 어떤 x와 C_j에 있는 y에 대해, 방향이 있는 edge (x,y)를 포함한다면, E^SCC에 (v_i, v_j)인 edge가 있다. 다른 방식으로 봐보면, G의 같은 SCC내에 incident 정점들이 있는 모든 edges를 대조 하여, 최종 graph는 G^SCC이다. 그림 22.9(c)는 그림 22.9(a)에서의 그래프의 component graph를 보여준다.
Lemma 22.13
C와 C'가 방향이 있는 그래프 G = (V,E)에서 별개의 SCC라고 하고, u,v는 C에 속하고, u', v'는 C'에 속한다고 하고, G는 u->u` 경로를 포함한다고 가정하자. 그러면 G는 또한 v'->v의 경로를 포함할 수 없다.
Proof 만약 G가 v'->v의 경로를 포함한다면, 그러면 그것은 u->u'->v'와 v'->v->u의 경로들을 포함한다. 따라서, u와 v'는 서로 도달가능하다. 거기에서 C와 C'가 별개의 SCC라고 가정과 대조된다.
우리는 첫 번째 DFS에서 연산된 마무리 시간의 내림차순으로 두 번째 DFS에서의 정점들을 고려하여, 우리는 본질적으로 위상정렬된 순으로 component graph의 (G의 한 SCC에 일치하는) 정점들을 방문한다는 것을 볼 것이다.
STRONGLY-CONNECTED-COMPONENTS 절차는 두 개의 DFS를 수행하기 때문에, 우리가 u.d와 u.f를 다룰 때 모호함의 가능성이 있다. 이 섹션에서, 이러한 값들은 line 1에서 항상 DFS의 첫 번째 호출에 의해 연산된 발견시간과 마무리 시간을 언급한다.
우리는 정점들의 집합에 대해 발견시간과 마무리 시간에 대한 표기법을 확장한다. 만약 U집합이 V에 속한다면, 그러면 우리는 d(U) = min(u in U){u.d}와 f(U) = max(u in U){u.f}를 정의한다. 즉, d(U)와 f(U)는 U에서 어떤 정점이든지 개별적으로 가장 빠른 발견시간이고 가장 최근의 마무리 시간이다.
다음의 lemma와 그것의 corollary는 SCC와 첫 번째 DFS에서의 마무리시간에 관련된 한 가지 주된 특징을 준다.
Lemma 22.14
C와 C'가 방향이 있는 그래프 G = (V,E)에 있는 별개의 SCC라고 하자. E에 (u,v)가 있고, u는 C에 속하고, v는 C'에 속한다고 가정하자. 그러면 f(C) > f(C')이다.
Proof 우리는 어떤 SCC, C 또는 C'가 DFS 동안에 첫 번째 발견된 정점을 가지는지에 따라 두 가지 경우를 고려한다.
만약 d(C) < d(C')라면, x가 C에서 처음으로 발견된 정점이라고 하자. x.d 시간에서 C와 C'에 있는 모든 정점은 white이다. 그 시간에, G는 x로부터 하얀색 정점들만으로 구성된 C에서의 각 정점으로 가는 한 경로를 포함한다. (u,v)가 E에 있기 때문에, C'에 있는 어떤 정점 w에 대해, 또한 G에서 x.d시간에 x에서 w로 가는 오직 하얀색 정점들로만 구성된 한 경로가 있다: x->u -> v->w. white-path theorem에 의해, C와 C'에 있는 모든 정점들은 DF-tree에서 x의 후손이 된다. Corollary 22.8에 의해, x는 그것의 후손의 어떤 것이든지 가장 나중 시간을 갖는다. 그래서 x.f = f(C) > f(C') 이다.
만약 대신에 우리가 d(C) > d(C')를 가졌다면, y를 C'에서 발견된 첫 번째 정점이라고 하자. y.d 시간에, C'에 있는 모든 정점들은 white이고, G는 오직 하얀색으로만 구성된 C'에서 y에서 각 정점으로 가는 한 경로를 가진다. white-path theorem에 의해, C'에 있는 모든 정점들은 DF-tree에서 y의 후손이되고, Corollary 22.8에 의해, y.f = f(C')이 된다. y.d 시간에 C에 있는 모든 정점들은 하얀색이다. C에서 C'로가는 (u,v) edge가 있기 때문에, Lemma 22.13은 C'에서 C로 가는 경로가 없다라는 것을 암시한다. 그러므로 C에 있는 어떠한 정점도 y로부터 도달할 수 없다. y.f의 시간에 그러므로, C에 있는 모든 정점은 여전히 하얀색이다. 따라서, C에 있는 어떤 정점 w에 대해, 우리는 w.f > y.f를 갖고 이것은 f(C) > f(C')를 암시한다.
다음의 corollary는 우리에게 G^t에서 다른 SCC사이를 가는 각 edge가 더 빠른 마무리 시간을 가진 한 요소에서 더 나중에 끝난 요소로 간다는 것을 말해준다.
Corollary 22.15
C와 C'가 방향이 있는 그래프 G = (V,E)에서 별개의 SCC라고 하자. E^t에 (u,v) edge가 있다고 하고, u는 C에 속하고 v는 C'에 속한다고 가정하자. 그러면 f(C) < f(C')이다.
Proof (u,v)가 E^t에 있기 때문에, 우리는 E에 (v,u)를 갖는다. G와 G^t의 SCC는 같기 때문에, Lemma 22.14는 f(C) < f(C')인 것을 암시한다.
Corollary 22.15는 왜 SCC 알고리즘이 작동하는지에 대해 이해하는 열쇠를 제공한다. 우리가 G^t에 두 번째 DFS를 수행할 때 무슨 일이 일어나는지 조사해보자. 우리는 마무리 시간 f(C)가 maximum인 SCC인 C로 시작한다. 그 탐색은 C에 있는 어떤 정점 x에서 시작하고, 그것은 C에 있는 모든 정점들을 방문한다. Corollary 22.15에 의해, G^t는 C에서 어떤 다른 SCC 컴포넌트로 가는 edges를 갖고 있지 않다. 그래서 x로부터 시작하는 그 탐색은 어떤 다른 component에 있는 정점들을 방문하지 않을 것이다. 따라서, x를 루트로 하는 트리는 정확히 C의 정점들을 포함한다. C에 있는 모든 정점을 방문하는 것을 완료하고 나서, line 3에서의 탐색은 마무리 시간 f(C')가 C를 제외하고 다른 컴포넌트들에 비해 가장 큰 어떤 다른 SCC인 C' 에서 한 정점을 root로서 선택한다. 또 다시, 그 탐색은 C'에 있는 모든 정점들을 방문할 것이다. 그러나, Corollary 22.15에 의해, G^t에 있는 C'에서 어떤 다른 component로 가는 유일한 edges들은 C에 대한 것임에 틀림 없다. 그곳은 우리가 이미 방문했던 곳이다. 일반적으로, line 3에서 G^t의 DFS가 어떤 SCC를 방문 할 때, 그 component 밖으로 나가는 어떤 edges들은 그 탐색이 이미 방문한 component임에 틀림 없다. 그러므로 모든 depth-first tree는 정확히 하나의 Strongly Connected Component이다. 다음의 정리는 이 주장을 공식화한다.
Theorem 22.16
STRONGLY-CONNECTED-COMPONENTS 절차는 정확히 그것의 입력으로서 제공된 방향이 있는 그래프 G의 SCC를 연산한다.
Proof 우리는 line 3에서 각 tree의 정점들이 SCC를 형성하는 G^t에 대한 DFS에서 발견된 DF-tree의 숫자에 대한 귀납으로 주장을 한다. 그 귀납 가설은 line 3에서 만들어진 처음의 K번째 trees가 SCC라는 것이다. k = 0일 때, 귀납에 대한 기저는 자명하다.
귀납 단계에서, 우리는 line 3에서 만들어진 k번째 DF-tree 각각이 SCC라고 가정하고, 그리고 우리는 만들어진 (k + 1)번째 tree를 고려한다. 이 tree의 root가 정점 u라고 하고, u가 SCC인 C안에 있다고 하자. line 3에서 DFS에서 roots를 고르는 방식 때문에, C를 제외하고 아직 방문되어야 할 SCC인 C'에 대해 u.f = f(C) > f(C') 이다. 귀납 가설에 의해, 탐색이 u를 방문할 때, C의 모든 정점들은 white이다. white-path theorem에 의해, 그러므로, C의 모든 정점들은 그것의 DF-tree에서 u의 후손들이다. 게다가, Corollary 22.15와 귀납가설에 의해, C를 떠나는 G^t에 있는 어떤 edges들은 이미 방문된 SCC에 대한 것임에 틀림없다. 따라서, C를 제외한 어떤 SCC에서 든지, 어떠한 정점도 G^t의 DFS동안에 u의 후손이 아닐 것이다. 따라서, u를 root로하는 G^t에서 DF-tree의 정점들은 정확히 한 개의 SCC를 형성하고, 이것은 귀납 단계와 증명을 완료짓는다.
여기에 두 번째 DFS가 어떻게 연산하는지를 바라보는 다른 방법이 있다. G^t의 (G^t)^SCC component graph를 고려해보자. 만약 우리가 (G^t)^SCC 의 한 정점에 두 번째 DFS에서 방문되는 각 SCC를 사상시킨다면, 그 두 번째 DFS는 위상정렬된 순서의 역으로 (G^t)^SCC 의 정점들을 방문한다. 만약 우리가 (G^t)^SCC의 edges들을 반전시킨다면, 우리는 ((G^t)^SCC )^t 그래프를 얻게 된다. (G^t)^SCC = G^SCC이기 때문에, (see Exercise 22.5-4), 두 번째 DFS는 위상 정렬된 순서로 G^SCC의 정점들을 방문한다.
많은 프로그램은 사건들 사이에서 우선을 가리키기위해 방향이 있는 비순환 그래프들을 사용한다. 그림 22.7은 Professor Bumstead가 아침에 옷을 입을 때 발생하는 한 예시를 준다. 그 교수는 다른 것들 전에 어떤 의류들을 입어야 한다. (예를들어, 신발전에 양말). 다른 아이템들은 어떤 순서 든지로 넣어질지도 모른다 (예를들어 양말과 바지) 그림 22.7(a)의 dag에서 방향이 있는 edge (u,v)는 의류 u가 의류 v전에 입어져야만 한다는 것을 가리킨다. 그러므로 이 dag의 위상 정렬은 입혀질 순서를 준다. 그림 22.7(b)는 수평선에 따라 정점들에게 ordering한것으로서 위상적으로 정렬된 dag을 보여준다. 모든 방향이 있는 edges가 왼쪽에서 오른쪽으로 가도록.
다음의 간단한 알고리즘은 dag를 위상적으로 정렬한다:
TOPOLOGICAL-SORT(G) 1 call DFS(G) to compute finishing times v.f for each vertex v 2 as each vertex is finished, insert it onto the front of a linked list 3 return the linked list of vertices
그림 22.7(b)는 어떻게 위상적으로 정렬된 정점들이 그것들이 끝나는 시간의 역순으로 나타나는 지를 보여준다.
우리는 Ө(V + E) 시간안에 위상정렬을 수행할 수 있다. 왜냐하면 DFS는 Ө(V+E) 시간이 걸리고, |V| 정점 각각을 linked list의 앞에 넣는데 O(1)이 걸리기 때문이다.
우리는 방향이 있는 비순환 그래프를 특징화하는 다음의 주된 lemma를 사용하여 이 알고리즘의 정당성을 증명한다.
Lemma 22.11
방향이 있는 그래프 G는 비순환이다 <=> DFS가 어떤 back edges를 만들어 내지 않는다.
Proof =>: DFS가 back edge (u,v)를 만든다고 가정하자. 그러면 정점 v는 depth-first forest에서 정점 u의 한 조상이다. 따라서, G는 v에서 u로가는 한 경로를 포함하고 그래서 back edge(u,v)는 한 사이클은 완성짓는다.
<=: G가 cycle c를 포함한다고 가정하자. 우리는 G의 DFS가 back edge를 만들어낸다는 것을 보여준다. v가 c에서 발견될 첫 번째 정점이라고 하고, (u,v)가 c에서 선행하는 edge라고 하자. v.d 시간에, c의 정점들은 v에서 u로가는 white vertices에 대한 한 경로를 형성한다. white-path 정리에 의해, 정점 u은 depth-first forest에서 v의 후손이 된다. 그러므로, (u,v)는 back edge이다.
Theorem 22.12
TOPOLOGICAL-SORT는 그것의 입력으로서 제공된 방향이 있는 비순환 그래프의 위상 정렬을 만들어낸다.
Proof DFS가 그것의 정점들에 대한 마무리 시간을 결정하기 위해 주어진 dag G = (V,E)에서 작동한다고 가정하자. V에 있는 별개의 정점의 쌍 u,v에 대해, 만약 G가 u->v의 edge를 포함한다면, 그러면 v.f < u.f라는 것을 보여주는 것은 충분하다. DFS(g)에 의해 탐사되는 어느 edge(u,v)에 대해 고려하자. 이 edge가 탐험되었을 때, v는 gray가 될 수 없다. 왜냐하면 그러고나서 v는 u의 조상이 될것이고 (u,v)의 back edge가 될 것이기 때문이다. 이것은 22.11 Lemma와 모순이 된다. 그러므로 v는 white 또는 black이여야 한다. 만약 v가 white라면, 그것은 u의 후손이되고, 그래서 v.f < u.f가 된다. 만약 v가 black이라면, 그것은 이미 끝나졌다. v.f가 이미 설정되었기 되도록. 우리는 여전히 u로부터 탐사중이기 때문에, 우리는 아직 u.f에 대해 timestamp를 할당해야만 하고, 그래서 우리가 그렇게 한다면, 우리는 v.f < u.f를 또한 갖을 것이다. 따라서, dag에 있는 어떤 edge (u,v)에 대해, 우리는 v.f < u.f 가지고, 정리에 대해 증명한다.
22.5 Strongly connected components
우리는 이제 DFS의 고전적인 적용을 고려한다: 방향이 있는 그래프를 strongly connected components로 분해하기. 이 섹션은 두 개의 DFS를 사용하여 어떻게 그렇게 하는지를 보여준다. 방향이 있는 그래프와 작동하는 많은 알고리즘은 그러한 분해로 시작한다. 그래프를 strongly connected compontes(SCC)로 분해한 후에, 그러한 알고리즘은 각각에 대해 별개로 작동하고, 그러고나서 컴포넌트들의 사이에 있는 연결 구조에 따라서 솔루션들을 합친다.
Appendix B로부터 한 방향이 있는 그래프 G = (V,E)의 하나의 SCC는 V에 포함되는 정점들의 maximal 집합 C라는 것을 상기하라. 이것은 C에 있는 정점들 u,v의 모든 쌍에 대해, 우리가 u -> v와 v ->u를 둘 다 갖게 하기 위해서이다; 즉, 정점 u와 v는 서로에게 접근가능하다. 그림 22.9는 한 예제를 보여준다.
한 그래프 G = (V, E)의 한 SCC를 찾는 우리의 알고리즘은 G의 전치행렬을 사용한다. 그리고 우리는 그 전치행렬은 연습문제 22.1-3에서 G^t = (V, E^t)로 정의했었다. 거기에서
E^t = {(u,v): (v,u) in E} 이다. 즉, E^t는 그들의 방향이 역전된 G의 edges로 구성된다. G의 인접리스트 표기법이 주어진다면, G^t를 만드는 시간은 O(V + E)이다. G와 G^t가 정확히 같은 SCC를 같는 것을 관찰하는 것은 흥미롭다: u와 v는 G에서 서로 접근 가능하다 <=> 그들은 G^t에서 서로 접근가능 하다. 그림 22.9(b)는 그림 22.9(a)에서 그래프의 전치행렬을 보여주고, SCC들이 그림자표시 되어있다.
다음의 선형-시간의 (즉, Ө(V + E) 시간) 알고리즘은 한 방향이 있는 그래프 G = (V,E)의 SCC를 두 개의 DFS를 사용하여 연산한다. 하나는 G에 하나는 G^t에.
STRONGLY-CONNECTED-COMPONENTS(G) 1 call DFS(G) to compute finishing times u.f for each vertex u 2 compute G^t 3 call DFS(G^t), but in the main loop of DFS, consider the vertices in order of decreasing u.f (as computed in line 1) 4 output the vertices of each tree in depth-first forest formed in line 3 as a separate strongly connected component
이 알고리즘 뒤에 있는 아이디어는 component graph G^SCC = (V^SCC, E^SCC)의 주요 특징으로부터 온다. 우리는 그것을 다음과 같이 정의한다. G가 C_1, C_2, ... , C_K인 SCC를 가진다고 가정하자. 그 정점의 집합 V^SCC는 {v_1, v_2, ..., v_k}이고, 그리고 그것은 G의 각각의 SCC C_i에 대해 정점 v_i를 포함한다. 만약 G가 C_i에 있는 어떤 x와 C_j에 있는 y에 대해, 방향이 있는 edge (x,y)를 포함한다면, E^SCC에 (v_i, v_j)인 edge가 있다. 다른 방식으로 봐보면, G의 같은 SCC내에 incident 정점들이 있는 모든 edges를 대조 하여, 최종 graph는 G^SCC이다. 그림 22.9(c)는 그림 22.9(a)에서의 그래프의 component graph를 보여준다.
Lemma 22.13
C와 C'가 방향이 있는 그래프 G = (V,E)에서 별개의 SCC라고 하고, u,v는 C에 속하고, u', v'는 C'에 속한다고 하고, G는 u->u` 경로를 포함한다고 가정하자. 그러면 G는 또한 v'->v의 경로를 포함할 수 없다.
Proof 만약 G가 v'->v의 경로를 포함한다면, 그러면 그것은 u->u'->v'와 v'->v->u의 경로들을 포함한다. 따라서, u와 v'는 서로 도달가능하다. 거기에서 C와 C'가 별개의 SCC라고 가정과 대조된다.
우리는 첫 번째 DFS에서 연산된 마무리 시간의 내림차순으로 두 번째 DFS에서의 정점들을 고려하여, 우리는 본질적으로 위상정렬된 순으로 component graph의 (G의 한 SCC에 일치하는) 정점들을 방문한다는 것을 볼 것이다.
STRONGLY-CONNECTED-COMPONENTS 절차는 두 개의 DFS를 수행하기 때문에, 우리가 u.d와 u.f를 다룰 때 모호함의 가능성이 있다. 이 섹션에서, 이러한 값들은 line 1에서 항상 DFS의 첫 번째 호출에 의해 연산된 발견시간과 마무리 시간을 언급한다.
우리는 정점들의 집합에 대해 발견시간과 마무리 시간에 대한 표기법을 확장한다. 만약 U집합이 V에 속한다면, 그러면 우리는 d(U) = min(u in U){u.d}와 f(U) = max(u in U){u.f}를 정의한다. 즉, d(U)와 f(U)는 U에서 어떤 정점이든지 개별적으로 가장 빠른 발견시간이고 가장 최근의 마무리 시간이다.
다음의 lemma와 그것의 corollary는 SCC와 첫 번째 DFS에서의 마무리시간에 관련된 한 가지 주된 특징을 준다.
Lemma 22.14
C와 C'가 방향이 있는 그래프 G = (V,E)에 있는 별개의 SCC라고 하자. E에 (u,v)가 있고, u는 C에 속하고, v는 C'에 속한다고 가정하자. 그러면 f(C) > f(C')이다.
Proof 우리는 어떤 SCC, C 또는 C'가 DFS 동안에 첫 번째 발견된 정점을 가지는지에 따라 두 가지 경우를 고려한다.
만약 d(C) < d(C')라면, x가 C에서 처음으로 발견된 정점이라고 하자. x.d 시간에서 C와 C'에 있는 모든 정점은 white이다. 그 시간에, G는 x로부터 하얀색 정점들만으로 구성된 C에서의 각 정점으로 가는 한 경로를 포함한다. (u,v)가 E에 있기 때문에, C'에 있는 어떤 정점 w에 대해, 또한 G에서 x.d시간에 x에서 w로 가는 오직 하얀색 정점들로만 구성된 한 경로가 있다: x->u -> v->w. white-path theorem에 의해, C와 C'에 있는 모든 정점들은 DF-tree에서 x의 후손이 된다. Corollary 22.8에 의해, x는 그것의 후손의 어떤 것이든지 가장 나중 시간을 갖는다. 그래서 x.f = f(C) > f(C') 이다.
만약 대신에 우리가 d(C) > d(C')를 가졌다면, y를 C'에서 발견된 첫 번째 정점이라고 하자. y.d 시간에, C'에 있는 모든 정점들은 white이고, G는 오직 하얀색으로만 구성된 C'에서 y에서 각 정점으로 가는 한 경로를 가진다. white-path theorem에 의해, C'에 있는 모든 정점들은 DF-tree에서 y의 후손이되고, Corollary 22.8에 의해, y.f = f(C')이 된다. y.d 시간에 C에 있는 모든 정점들은 하얀색이다. C에서 C'로가는 (u,v) edge가 있기 때문에, Lemma 22.13은 C'에서 C로 가는 경로가 없다라는 것을 암시한다. 그러므로 C에 있는 어떠한 정점도 y로부터 도달할 수 없다. y.f의 시간에 그러므로, C에 있는 모든 정점은 여전히 하얀색이다. 따라서, C에 있는 어떤 정점 w에 대해, 우리는 w.f > y.f를 갖고 이것은 f(C) > f(C')를 암시한다.
다음의 corollary는 우리에게 G^t에서 다른 SCC사이를 가는 각 edge가 더 빠른 마무리 시간을 가진 한 요소에서 더 나중에 끝난 요소로 간다는 것을 말해준다.
Corollary 22.15
C와 C'가 방향이 있는 그래프 G = (V,E)에서 별개의 SCC라고 하자. E^t에 (u,v) edge가 있다고 하고, u는 C에 속하고 v는 C'에 속한다고 가정하자. 그러면 f(C) < f(C')이다.
Proof (u,v)가 E^t에 있기 때문에, 우리는 E에 (v,u)를 갖는다. G와 G^t의 SCC는 같기 때문에, Lemma 22.14는 f(C) < f(C')인 것을 암시한다.
Corollary 22.15는 왜 SCC 알고리즘이 작동하는지에 대해 이해하는 열쇠를 제공한다. 우리가 G^t에 두 번째 DFS를 수행할 때 무슨 일이 일어나는지 조사해보자. 우리는 마무리 시간 f(C)가 maximum인 SCC인 C로 시작한다. 그 탐색은 C에 있는 어떤 정점 x에서 시작하고, 그것은 C에 있는 모든 정점들을 방문한다. Corollary 22.15에 의해, G^t는 C에서 어떤 다른 SCC 컴포넌트로 가는 edges를 갖고 있지 않다. 그래서 x로부터 시작하는 그 탐색은 어떤 다른 component에 있는 정점들을 방문하지 않을 것이다. 따라서, x를 루트로 하는 트리는 정확히 C의 정점들을 포함한다. C에 있는 모든 정점을 방문하는 것을 완료하고 나서, line 3에서의 탐색은 마무리 시간 f(C')가 C를 제외하고 다른 컴포넌트들에 비해 가장 큰 어떤 다른 SCC인 C' 에서 한 정점을 root로서 선택한다. 또 다시, 그 탐색은 C'에 있는 모든 정점들을 방문할 것이다. 그러나, Corollary 22.15에 의해, G^t에 있는 C'에서 어떤 다른 component로 가는 유일한 edges들은 C에 대한 것임에 틀림 없다. 그곳은 우리가 이미 방문했던 곳이다. 일반적으로, line 3에서 G^t의 DFS가 어떤 SCC를 방문 할 때, 그 component 밖으로 나가는 어떤 edges들은 그 탐색이 이미 방문한 component임에 틀림 없다. 그러므로 모든 depth-first tree는 정확히 하나의 Strongly Connected Component이다. 다음의 정리는 이 주장을 공식화한다.
Theorem 22.16
STRONGLY-CONNECTED-COMPONENTS 절차는 정확히 그것의 입력으로서 제공된 방향이 있는 그래프 G의 SCC를 연산한다.
Proof 우리는 line 3에서 각 tree의 정점들이 SCC를 형성하는 G^t에 대한 DFS에서 발견된 DF-tree의 숫자에 대한 귀납으로 주장을 한다. 그 귀납 가설은 line 3에서 만들어진 처음의 K번째 trees가 SCC라는 것이다. k = 0일 때, 귀납에 대한 기저는 자명하다.
귀납 단계에서, 우리는 line 3에서 만들어진 k번째 DF-tree 각각이 SCC라고 가정하고, 그리고 우리는 만들어진 (k + 1)번째 tree를 고려한다. 이 tree의 root가 정점 u라고 하고, u가 SCC인 C안에 있다고 하자. line 3에서 DFS에서 roots를 고르는 방식 때문에, C를 제외하고 아직 방문되어야 할 SCC인 C'에 대해 u.f = f(C) > f(C') 이다. 귀납 가설에 의해, 탐색이 u를 방문할 때, C의 모든 정점들은 white이다. white-path theorem에 의해, 그러므로, C의 모든 정점들은 그것의 DF-tree에서 u의 후손들이다. 게다가, Corollary 22.15와 귀납가설에 의해, C를 떠나는 G^t에 있는 어떤 edges들은 이미 방문된 SCC에 대한 것임에 틀림없다. 따라서, C를 제외한 어떤 SCC에서 든지, 어떠한 정점도 G^t의 DFS동안에 u의 후손이 아닐 것이다. 따라서, u를 root로하는 G^t에서 DF-tree의 정점들은 정확히 한 개의 SCC를 형성하고, 이것은 귀납 단계와 증명을 완료짓는다.
여기에 두 번째 DFS가 어떻게 연산하는지를 바라보는 다른 방법이 있다. G^t의 (G^t)^SCC component graph를 고려해보자. 만약 우리가 (G^t)^SCC 의 한 정점에 두 번째 DFS에서 방문되는 각 SCC를 사상시킨다면, 그 두 번째 DFS는 위상정렬된 순서의 역으로 (G^t)^SCC 의 정점들을 방문한다. 만약 우리가 (G^t)^SCC의 edges들을 반전시킨다면, 우리는 ((G^t)^SCC )^t 그래프를 얻게 된다. (G^t)^SCC = G^SCC이기 때문에, (see Exercise 22.5-4), 두 번째 DFS는 위상 정렬된 순서로 G^SCC의 정점들을 방문한다.
댓글 없음:
댓글 쓰기