Topological Sort

DAG (Directed acyclic graph == 사이클이 없는 그래프) 가 주어졌을 때, 노드를 정렬하는 방법

노드를 일렬로 (linear) 정렬하는 방법이다.

    규칙은?? edge의 방향이 무조건 왼쪽 -> 오른쪽 이도록 해준다.

 

총 3가지 방법이 있다!

 

topoplogical sort는 사이클이 없는 그래프에서만 가능하다 (사이클이 생기면 정렬못함)

== 즉 topoplogical sort가 정상적으로 동작하지 않으면, 해당 그래프에 사이클이 있다는 뜻도 된다

 

Indegree Array

모든 노드들의 incoming edge 개수를 저장하고, 여기서 0값을 가지는 노드부터 정렬해주는 방법

=> incoming edge를 배열에 저장하므로, 0값을 찾는것 * 모든 vertex마다 이루어짐

== 시간복잡도가 O(V^2)이 된다 (너무 오래걸림!!)

 

1. 모든 노드들의 incoming edge를 배열에 저장해준다. (본인으로 들어오는 화살표 개수)

2. 여기서부터 반복을 시작하는데...

    a. 배열에서 incoming edge가 0인 노드를 랜덤으로 하나 선택해서 linear array에 넣어준다.

    b. 선택한 노드가 향하는 다른 노드의 incoming edge값을 1 줄여준다 (outgoing edge)

    c. 다시 위 과정을 반복한다.

3. 모든 node의 incoming edge값이 -1이 되면 끝난다.

 

Indegree stack

indegree Array에서 시간복잡도에 문제가 생긴건,,, incoming edge 개수를 array에 냅다 넣어버렸기 때문이다!

그래서 0을 찾을 때 매번 array 전체를 탐색해야 해서 n^2라는 시간복잡도가 나왔다.

stack을 이용하면?? 굳이 0을 찾지 않아도 될 수 있다!

 

1. 모든 노드들의 incoming edge 개수를 "배열"에 저장한다.

2. 이 중 값이 0인것들만 indegree stack에 쌓아준다.

3. 여기서부터 반복을 시작하는데....

    a. stack에서 노드 하나를 pop해준다 (incoming edge값이 0인거 확정임!)

    b. 그 노드를 linear array에 넣어주고, outgoing edge에 있는 노드들의 incoming edge값을 줄여준다.

        이 과정에서 줄였는데 0이 되는 노드가 있으면?? stack에 넣어준다!

    c. 다시 위 과정을 반복한다.

4. 모든 노드들의 incoming edge값이 -1이 되면 끝난다.

 

=> 0을 찾을필요가 없으므로,,, O(V + E) 라는 시간복잡도가 나온다! 굿굿

 

DFS 이용하기

graph를 dfs로 탐색할 때, discover time/ finish time을 찍어줄 수 있다

이 때 finish time을 기준으로 내림차순 정렬을 해주면 topological sort가 된다!

 

---

stack이나 DFS를 사용해주는게 좀 더 이해하기 편한것같다..!

dfs가 구현에는 제일 간편할것 같기도 하궁,,,