[알고리즘 #8] Graph Algorithms(3)

 

DAG ( Directed Acyclic Graphs )

• Cycle이 존재하지 않는 Directed 그래프이다.
• Cycle 존재하지 않아서 다양한 문제를 효율적으로 해결가능하다.
• Topological sort : DAG G 의 vertex들을 아래 순서에 따라 sorting 하는 것

보기 편하게 sort / 가장 화살표를 시작하는게  source 가장 끝 목적지가 sink 이다.

 

vertex 를 방문한 순서를 vertex 위에 나타내보았다. 첫번째 요소는 previsit 시의 순서이고 두번째요소는 postvisit 시의 순서이다. 그 후 postvisit 이 decreasing 하는 순서대로 나열하면 topological sort 이다.

 

edge(u, v) 가 존재할 경우 , vertex u 는 vertex v 보다 순서가 앞이다.

• DAG 의 vertex 들은 반드시 topological sort 가능하다.
• Topological sorting 한 결과는 unique 하지 않을 수 있다. 
• Topological sort 는 O(n+m) 시간이 걸린다 -> DFS 트리 이용

DFS를 수행하면서 postvisit(v) 할 때마다 , v를 stack 에 push (DFS 종료 후 차례대로 pop해준다) Postvisit number 역순은 항상 topological order 을 만족
// Postvisit(v) : Vertex v 에 대한 DFS 함수가 완전히 종료되기 바로 직전에 수행하는 연산
// Kahn's Algorithm : ource 중 하나 출력 -> 해당 source 삭제 후의 graph에 대해 같은 과정을 recursively 하게 반복( vertex 존재하지 않을때까지)

• 만약 post(u) < post(v) 인 edge(u, v) 가 존재한다면, 해당 edge 는 back edge 가 되어 DAG 가 될 수 없다. 

 

 

 

Single source shortest Path / Longest Path in DAG

 

Topological Sort 후에 source에서 부터 순서대로 vertex 들을 scan 하면서 source 로 의 shortest path 의 길이를 update 한다. O(m+n) 시간에 해결할 수 있다.

Longest Path 또한 일반적인 graph 에서는 NP-hard 문제지만 DAG 에서는 각 weight 에 -1 을 곱 한 다음 해당 graph 에 대해 shortest path 문제를 해결하면 된다 (최종적으로 구한 답에 다시 -1 을 곱해 줌).

 

(*NP는 비결정론적 튜링 기계를 사용해서 polynomial time내에 답을 구할 수 있는 문제의 집합이다. 다시 말하면, yes 또는 no로 답할 수 있는 문제에서 yes라고 답을 주었을 때, 그 답이 정말 yes가 맞는지를 polynomial time안에 확인할 수 있으면 그 문제를 NP문제라고 한다.)

 

다음 그림은 DAG 그래프가 있을 때, vertex s 에서 shortest path 를 업데이트 해주는 과정을 나타낸 것이다. 처음에는 무한대로 초기화 되어있는 값을 source 에서부터 스캔하면서 만약 더 shortest path 가 있다면 update 해준다.

 

코드로 표현하면 다음과 같다.

우선 모든 vertex 를 순회하한다. 예를들어 현재 u라는 vertex를 체크할 때, L(u) 에 속한 원소들을 한 번씩 확인하면서 shortest path를 update 해준다. L(u) 는 현재 순회중인 vertex와 인접한 vertex set 이다. 업데이트 할 때는 기존에 저장되어있던 거리에서 d[u] 에 edge 의 가중치인 w(u,v )를 더한값이 그냥 d[v] 기존값보다 작다면 d[v] 의 shortest path를 업데이트 해주는 방식으로 진행된다. ( 기존 path 거리와 u를 거쳤을 때 거리 중 더 짧은 값을 취하는 방식이다.)

for(u ∈ V) // on topological order{
     for(v ∈ L(u)){
         if(d[u] + w(u, v) < d[v])
         {
          d[v] = d[u] + w(u, v); prev[v] = u;
         }
}}
// L(u) : Set for Adjacency Vertices of Vertex 'u' // d[v] : Minimum Cost to connect with Vertex 'v' and Spanning Tree

 

Counting the number of distinct paths

DAG 의 vertex x 에 대해 paths(x) 를 source 에서 x로의 서로 다른 path 의 개수라 할 때, paths(x) 구하기

Topological sort 후에 DP 를 이용하여 계산 가능하다. Source 를 s 라 하자.

 

Base case )

paths (s) = 1

s 보다 topological order 가 앞인 모든 vertex x 에 대해 paths(x) = 0

 

Inductive step)

Vertex s 뒤에 있는 vertex x 의 indegree (차수)가 k 라 하자. 이 경우 edge (s1 , x) , (s2 , x), …,(sk , x) 가 있다 하면 paths (x) = paths(s1 ) + paths(s2 ) + … + paths(sk ) 가 된다.

paths(x) 는 x로 들어오는 모든 edge에 대해 paths(해당 들어오는 vertex) 를 더해주면된다. paths(6) 은 paths(2) + paths(3) 으로 나타낼 수 있고 paths(2)와 paths(3) 은 각각 더 작은 pahts 들로 쪼개지므로 DP 를 활용하여 풀 수 있다.

 

ex ) SPOJ - FISHMONGER

 

-도시 수 3 ≤ n ≤ 50, 남은 시간 1 ≤ t ≤ 1000, n x n matrix 두 개가 주어짐 (각각 두 도시간 의 이동시간 및 통행료를 정의한 matrix).

-항구 (도시 0) 에서 시장 (도시 n-1) 로 가는 경로를 찾아야 함. 단 최대한 적은 통행료를 지불하면서 t 시간안에 시장에 도착해야 함. 모든 도시를 다 방문할 필요는 없음.

-> 단순히 시간을 edge 의 weight 로 정의한 뒤 Dijkstra algorithm 을 적용할 경우 통행료에 대한 조건을 만족할 수 없다 (통행료로 정의해서 풀어도 마찬가지).

 

=> Solution = 주어진 graph 를 DAG 로 변환!

-각 vertex 를 (장소, 남은 시간) 으로 구성된 pair 라 가정하면, 입력 받은 두 matrix 를 바탕으로 DAG 을 위의 오른쪽과 같이 구성할 수 있다. - 예를 들어 항구->도시 A 간에 이동 시간이 5 만큼 소요되며, 해당 구간의 통행료가 2인 경우 (항구, 7) -> (A, 2) 로 의 edge 를 생성할 수 있으며, 해당 edge 의 cost 는 2가 된다.

-위에서 정의한 그래프는 무조건 DAG 이 되며 (Why?) 남은 시간이 negative 가 되는 경우는 없으므로, t 정의한 DAG 의 vertex 는 최대 nt 개이다.

- 따라서 위 DAG에 에서 single-source shortest path (여기서 path 길이 = 총 통행료) 알고리즘을 적용하 면 O(n2 t) 시간안에 문제를 해결할 수 있다.

 

 

ex) UVa - Injured Queen Problem

 

Strongly Connected Components

직관적으로 생각하면 "강하게 연결되어 있다" 는 "서로서로 연결되어있다." 이므로 만약 a에서 b로 갈수 있고 b에서 a로도 갈 수 있다면 Strongly connected 이다 ! 만약 집합들 사이에서 strongly connected 하다면 Strongly connected component 라고 하고 아래 그림을 참고하면 쉽다.

 

• directed graph 에서 u에서 v로 가는 path 존재하고 w에서 v로의 path 존재하면 Strongly connected 하다.
• Strongly connected component G' of G : G의 maximal strongly connected subgraph ( G 의 strongly connected component 는 G의 vertex 들을 partitoning 한다. )

 

• G의 모든 Strongly connected component 찾기

SOLUTION 1

Directed graph G 에서 모든 edge 들의 방향을 뒤집은 graph 를 G^R 이라고 하자. 
G의 adjacency list 가 주어졌을때 list 상의 elemet 들을 하나씩 scan 하는 방법으로 
G^R 의 adjacency list 를 O(n+m) 시간에 구할 수 있다.


S1 ⊂ G / S2 ⊂ G^R 
if) a,b E S1  ∩ S2
G에서 v->a->b // G^R 에서 b->a
maximality 증명 _)  만약 SCC 포함되지 않는 vertex존재하는데 maximal 하다고 가정 -> 모순 발생 ! 

SOLUTION 2 : DAG 이용 ( Kosaraju's algorithm)

Directed graph G 에 대해 G의 각 SCC 를 하나의 vertex 로 두고, SC S1 에서 S2 로 가는 edge 가 존재하면 , edge(S1,S2) 를 추가한 directed graph 를 G^d 라고 하자.
Gd 의 sink 에 속한 아무 vertex 로부터 explore 시, strongly connected component 하나를 얻을 수 있다.
G^d  dnk  sink 에 속한 vertex 는 찾기힘들어서 source를 우선 찾는다. ( G^R  에서 postnum 가장 큰 애)

Property 2 : Gd 의 두 vertex (= G의 strongly connected component) S1, S2 에 대해 edge (S1, S2) 가 있다면, G 에서 DFS 를 한 경우 S1 의 highest post number (S1 의 모든 vertex 들 중 post (v) 값 이 제일 큰 v) 는 언제나 S2 의 highest post number 보다 크다 (why)? - 여기서 post(v) 는 postvisit (v) 이 호출된 순서대로 숫자를 배정한 값을 의미.

Property 2 에 의해 Gd 의 source 는 G에서 highest post number 를 가진 vertex 를 무조건 포함한다.
Gd 와 GR d 는 같은 vertex set 을 가지고 있으며, Gd 의 sink 는 GR d 의 source 이다.
GR 에서 DFS 를 한 뒤 highest post order 를 가진 vertex (= GR d 의 source 에 속한 vertex) 는 Gd 의 sink 에 무조건 속해 있다 (problem 1 해결!)

Subproblem 2 : Gd 의 sink 에 해당한 strongly connected component 를 찾은 다음, 나머지 strongly connected component 들을 어떻게 찾을 수 있을까?

GR d 에서 source 를 제거하고, 해당되는 vertex 들을 G 에서 제거해도 property 2 에 의해 여전히 남아있는 vertex 들 중에서 가장 post number 가 큰 vertex 는 (새로운) GR d 의 source (=Gd 의 sink) 에 속해있다!!  남아있는 vertex 들에 대해 recursively 하게 수행 가능.