15. 방향 비싸이클 그래프와 위상 정렬 (DAG and Topological Sort)

방향싸이클이 존재하지 않는 방향 그래프를 방향 비싸이클 그래프^{Directed Acyclic Graph}라고 한다.
어떤 방향 그래프에서, 모든 $i<j$인 간선 $(v_i, v_j)$에 대해 노드들을 번호로 나열한 것을 위상 순서^{Topological Order}라 한다.

즉, 그래프가 DAG이면 위상순서를 가지며, 위상순서를 갖는 그래프는 DAG이다.

위상 정렬

위상 정렬이란, DAG에서 위상 순서를 얻는 절차를 말한다. 일반적인 위상 정렬 알고리즘과, DFS를 특화한 위상 정렬 DFS 알고리즘이 있다.

def topologicalSort(G):
    Q = queue()
    for u in G.vertices:
        if in(u) == 0: # 현재 노드의 진입 차수(노드 u로 들어오는 간선 수)가 0이면
            Q.enqueue(u)
    i=1 # 위상
    while !Q.isEmpty():
        u = Q.dequeue()
        u.topology = i # u의 위상, 선택사항임
        i += 1
        for e in u.outIncidentEdges: # u의 진출 간선들
            w = G.opposite(u, e) # 반대쪽 노드
            in(w) -= 1 # 반대쪽 노드의 진입차수 하나 줄이기
            if in(w) == 0:
                Q.enqueue(w)
    if i <= n: # 노드 수보다 위상이 적을 때
        print("G has a directed cycle")
    return

def topologicalSortDFS(G):
    n = len(G.vertices)
    for u in G.vertices:
        l(u) = Fresh
    for v in G.vertices:
        if I(v) == Fresh:
            rTopologicalSortDFS(G, v, n)
def rTopologicalSortDFS(G, v):
    I(v) = Visited
    for e in v.outIncidentEdges:
        w = opposite(v, e)
        if I(w) == Fresh:
            rTopologicalSortDFS(G, w)
        elif I(w) == Visited: #이미 위상이 정해져있음
            print("G is not DAG")
        else:
            # e is nontree edge
    v.topology = i
    n = n-1

두 버전 모두 $O(n+m)$ 시간이 소요되고, $G$의 위상순서를 계산한다. 이 때, 그래프 안에 싸이클이 존재하면 (DAG가 아니면) 일부 노드에 순위를 매기지 않고 중단한다.