Topological Sorting

Definition

• Tree Traversal을 먼저 참고하라. 
• 사이클이 없는 방향성 그래프 (Directed Acyclic Graph, DAG)에서 vertex u와 v사이에 edge u->v가 있다면 u가 v보다 먼저 출력되는 방식이다. 
• Task나 스케줄의 선후관계를 방향성 그래프로 표현할 때 일의 올바른 수행 순서를 표현하는데 적합하다. 

• 위의 그래프에서 topological sort의 순서는 5, 4, 2, 3, 1, 0 이다. 물론 4, 5, 2, 3, 1, 0도 가능하다. (즉 답이 여러 개다)
• DFS와 topological sort의 공통점은 방문한 노드(vertex)를 먼저 출력하고 이웃을 출력하는 방식인데, 차이점은 topological sort의 경우 해당 노드를 출력하기 전에 모든 선행 노드를 출력해야 한다는 점이다. 예를 들어, '0'전에 '5'를 출력하는 것은 DFS와 topological sort 모두 동일하니 topological sort의 경우 '0' 출력 전에 '4'도 출력해야 한다는 것이다. 
• 어쨌든 그 유사성으로 인해서 topological sort의 알고리즘은 DFS를 조금 수정하는 방식으로 작성 가능하다. (iterative방식의 수정은 좀 어려운 것 같고 recursive방식을 조금 수정하면 됨)
• DFS가 현재 노드를 visiting stack에 꺼내 방문(출력)하고 이웃을 visiting stack에 넣었다면, topological sort에서는 현재 노드를 visiting stack에서 꺼내고 이웃을 visiting stack에 넣은 뒤, 이웃의 방문이 완료되면 현재 노드를 sorting stack에 넣는다. 즉, 현재 노드가 sorting stack에 들어가는 시점이 이웃의 방문이 종료된 시점이라야 한다. (이 부분이 iterative 방식에서는 조금 까다로운 듯)
• 이후 traversal이 완료되면 sorting stack의 노드들을 꺼내면서 출력한다.

Code (recursive 방식)

• DFS가 현재 노드를 방문(출력)하고 이웃을 recursive하게 호출하는 방식이라면, 이웃의 방문이 완료되면 현재 노드를 (출력하는 것이 아니라) sorting stack에 넣는다. 
• Traversal의 시작점이 특정 노드가 아닌 graph 전체이므로 모든 node들에 대해 traversal을 시도해봐야 한다. 모든 traversal이 완료되면 sorting stack의 노드들을 꺼내면서 출력한다.

#include <stdio.h>
 
#define MAX_NODE  100000
#define MAX_EDGE  100000
#define TRUE  1
#define FALSE  0
 
typedef int BOOL;
 
typedef struct {
    int next_child;
    int last_child;
    BOOL visited; // for checking a cycle
} Vertex;
 
typedef struct {
    int index;
    int next;
} Child;
 
Vertex vertex_list[MAX_NODE];
Child child_list[MAX_EDGE];
int child_list_end; // the end of child list
int sorting_stack[MAX_NODE];
int sorting_stack_end; // the end index of sorting stack
 
// initialization code, this is also used for clearing data structures
void initialize(int number)
{
    int i;
    for (i = 0; i < number; i++) {
        vertex_list[i].last_child = -1;
        vertex_list[i].next_child = -1;
        vertex_list[i].visited = FALSE;
    }
    child_list_end = -1; // make an empty list
    sorting_stack_end = -1; // make an empty stack
}
 
void addEdge(int parent, int child)
{ ... }
 
void visiting(int index) 
{
    // Mark the current node as visited
    vertex_list[index].visited = TRUE;
 
    // Push back all unvisited child nodes to stack
    int j = vertex_list[index].next_child;
    while (j >= 0) {
        if (vertex_list[child_list[j].index].visited == FALSE)
            visiting(child_list[j].index);
        j = child_list[j].next;
    }
 
    sorting_stack[++sorting_stack_end] = index;
}
 
void topologicalSort(int number) 
{
    // Visit all vertices one by one
    int i;
    for (i = 0; i < number; i++)
        if (vertex_list[i].visited == FALSE)
            visiting(i);
 
    // Print sorting stack
    while (sorting_stack_end >= 0)
        printf("%d ", sorting_stack[sorting_stack_end--]);
}
 
int main(int argc, char** argv)
{
    initialize(6);
 
    addEdge(5, 2);
    addEdge(5, 0);
    addEdge(4, 0);
    addEdge(4, 1);
    addEdge(2, 3);
    addEdge(3, 1);
 
    printf("Topological sort is\n");
    topologicalSort(6);
 
    return 0;
}

• Recursive method인 visiting()에서 이웃노드들을 모두 방문하고 현재 노드를 sorting stack에 넣는 부분에 주의하라. (라인 56)