아래에서 설명할 기본적인 Topological sort는 DFS라고 할 수 있다.

• Indegree array만을 사용하는 경우
• Stack을 사용한 Topological sort

목표: DAG(Directed Acyclic Graph)에서 모든 edge가 왼쪽에서 오른쪽으로 가는 linear order를 생성하는 것

• 순서가 정해져있는 vertex들을 그 순서를 유지하며 선형 형태로 정렬하는 것.
• Topological sort의 결과는 여러 종류가 있을 수 있다.

Graph가 adjacency list를 사용한다고 가정하자.

Setting of Topological sort

• 각 vertex마다 In-degree의 개수를 배열에 저장한다.
• Running time of initial setting: $\theta(V + E)$

Topological sort의 과정

1. Indegree array에서 왼쪽에서부터 Indegree = 0 인 vertex를 찾고, 값을 -1로 변화시킨 후 뽑아낸다.

   • "-1"은 이미 종료되었다는 의미이다.
   • DFS에서의 BLACK

2. (1)에서 찾은 vertex에 adjacency한 vertex를 찾고 해당 vertex의 Indegree를 1씩 줄인다.

3. (1)에서 찾은 vertex에 adjacency한 모든 vertex에 대해 (2) 과정을 완료했다면 (1) ~ (2) 과정을 반복한다.

Running time of Topological sort

$O(V^2)$: 각 vertex마다 모든 Indegree array를 탐색해야한다.

• Indegree array의 크기 = $V$

Stack을 이용한 Topological sort

1. Indegree array에서 왼쪽에서부터 Indegree = 0 인 모든 vertex를 찾고, Stack에 추가한다.

   • "-1"을 사용하지 않는다.
   • Stack은 "Last in, first out" 이다.

2. Stack 가장 위에 있는 vertex에 대해 adjacency한 vertex를 찾고 해당 vertex의 Indegree를 1씩 줄인다.

3. (2)의 과정에서 Indegree = 0 이 된 vertex가 있다면, stack에 추가한다.

   • 다음으로 탐색하는 vertex가 되도록 한다.

4. Stack에 남아있는 vertex에 대해 (2) ~ (3)의 과정을 반복한다.

• 이 경우 Running time은 $\theta(V + E)$ 이다.
  • 기본적으로 V개의 vertex를 탐색한다.
  • Stack을 사용하기 때문에 모든 Indegree array를 탐색할 필요없이 E개의 edge만 탐색하면 된다.

다른 Topological sort 방법

1. Stack 대신 queue 사용

   • queue에 들어온 순서대로 처리, Indegree가 작은 순서대로 처리하게 된다.
   • 이는 DFS보다 BFS에 가깝다.

2. Out-degree 기준으로 처리

   • Out-degree = 0인 vertex를 오른쪽에서부터 정렬
   • Outdegree array를 사용하고 나머지 과정은 이전의 Topological sort와 비슷하다.

DFS 적용

• 가장 아래 그림은 Topological sort에 DFS 시작 시간, 끝나는 시간을 표시한 것이다.
• 결과를 보면 Topological sort는 DFS Finish time을 기준으로 내림차순으로 정렬되어있음을 확인할 수 있다.
• DFS에서의 방문 순서와 Topological sort의 순서에는 차이가 있다.
• 위에서 Stack을 사용한 Topological sort와 결과가 동일하다.

Running time of DFS in Topological sort

• $\theta(V + E)$: DFS를 적용하는 시간
• $O(1)$: Finished time의 내림차순으로 정렬하는 시간
• $\theta(V + E)$: Total running time

특징

• Edge (u, v)가 있다면 $v.f < u.f$ 이다.
• Topological sort의 대상 graph는 DAG이므로 back edge가 없다.
  • back edge가 존재하면 cycle이 형성되기 때문이다.
  • forwarding edge, tree edge, cross edge는 존재한다.

Cycle detector

DAG가 아닌 Graph에 대해 Topological sort를 수행한다고 가정하자.

• Topological sort를 진행하다가 stack이나 queue에 남은 vertex가 없으나, Indegree array가 모두 0이 아닌 경우에 cycle이 존재한다고 판단할 수 있다.

• Indegree array만 사용하는 경우, Indegree = 0 인 vertex가 없는데 Indegree = -1 이 아닌 vertex가 존재하는 경우에 cycle이 존재한다고 판단할 수 있다.