[ 알고리즘 ] 13. DFS - 활용

Topological sort
위상 정렬

 

DAG 에서 이루어진다.

= Directed Acyclic Graph ( 비순환 방향 그래프 )

 

위상 정렬이란 
DAG에서 정점을 선형으로 정렬하는 것을 말한다.

 

 

 

(u,v) 이렇게 있는 Edge는 u먼저 오고 그 뒤에 v가 오는 Edge를 말한다.

 

 

---

 

 

우선 DFS로 한 번 돌리고

Finished Time가 큰 순서대로 정렬을 한다.

 

 

주로 예시로는 옷을 입는 걸로 예시를 들 수 있다.

 

 

우선 (자신을 가리키는 게 없는 vertex에 한해서) 어디서 먼저 시작하든

제대로 된 결과가 나올 것이다.

 

Pants 를 먼저 입으면 안 되고, 그 전에 Underwear를 항상 먼저 입어야 하며,

Watch같은 경우는 무엇을 하든지 중간에 끼어들어서 할 수 있다.

 

Finish Time을 기준으로 봐야함

 

 

 

Time complexity : 1번  → 세타( V+E )

                             2번  → 세타(V)  =  ( V개의 node를 linked list에 넣으니까 )

 

 

---

 

 

 

 

f[u] > f[v] 인걸 증명해보자.

 

(u,v) edge를 거쳤고, u는 회색인 상태이다.

 

Case1) v = gray일 때 ,

             →(u,v)는 back edge이다 . Cycle이 된다.

         근데 DAG은 Cycle이 아니라서 Contradiction

 

Case2) v = white일 때 ,

             →v 가 u의 자식이 된다. → f[v] < f[u] 

 

 

 

 

Case3) v = black일 때 ,

            →v가 이미 끝났다는 의미 → f[v] < f[u] 

 

 

---

Connected Component

Connected 되어있는 것들끼리 확인하기 위해서는

아래 Psudo code 전에 해당  Tree에 대한 ID를 만든다.

 

DFS(G)에서 6번째 줄 다음에 id = label(u) 를 만들고, 이를 DFS-VISIT에 같이 넘겨주면 

함께 처리되는 Vertex들은 모두 label(u)로 되는 걸 알 수 있다.

 

DFS - VISIT에서 재귀될 때도 같이 넘겨준다!

 

 

 

 

 

 

---

Strongly Connected Component

 

 

Maximal sub-graph 는 어느 vertex에서도 다른 vertex로 갈 수 있는 걸 말한다.

= 왕복 가능한 Graph

= 모든 Vertex로의 Path가 있다.

 

초록색으로 되어있는 애들끼리는 SCC임

 

 

G  = 그냥 그래프

Gt  = Edge의 방향이 바뀐 것

 

둘 다 Strongly Connected임

 

---

 

 

 

1. DFS(G) 를 불러서 f[u]를 계산한다.

2. Gt 를 계산한다.

3. DFS(Gt) 를 부르고, f[u]가 큰 값부터 적용하여 계산한다.

4. 그 결과로 Strongly Connected component들 뭉텅이들이 나올 것이다.

 

 

 

● Time Complexity

 

: Matrix로 했을 때 → 세타(n^2)   // G matrix도 보고 , Gt matrix도 봐야 한다.

  Linked List → 세타 (V+E)          // Linked List 2개 (G, Gt)만 보면 된다.

 

 

 

---

 

 

SCC인 Component들을 하나의 Vertex로 간주한다.

 

그 안에서 가장 시작하는 Element의 Discovery Time을 갖고

그 안에서 가장 늦게 끝나는 Element의 Finished Time을 갖는다.

 

계산이 끝났으면 Transpose 된 Graph로 본다.

 

시작하는 순서는, 원래 Graph에서 Finish Time이 가장 컸던(늦게 끝난) vertex 먼저.

 

- 125 vertex 에서 돌고 끝난다.

▶ 34  vertex에서 돌고 끝난다

▶ 67 vertex에서 돌고 끝난다.

▶ 8 vertex에서 돌고 끝난다.

 

 

 

 

 

 

위에 이거 DFS(G) / DFS(Gt) 구하는 거 해봐야함

 

---

SCC 관련 Lemma

 

 

(전제 : 각 C나 C'안에서는 다 SCC 관계임)

 

C에 있는 vertex → C'에 있는 vertex 가 있으면

C' vertex에서 끝나야 C vertex가 끝날 수 있으므로

f(C) > f(C')

 

C가 C'보다 Finish Time이 크다면,

Gt에서는 C → C' 인 Edge가 있을 수 없다.

 

▼ 함 봐

 

(출처)

 

한동대학교 용환기교수님 - 알고리즘