[Computer Column] 위상정렬(topological sort)

위상정렬이란?

DAG(Directed Acyclic Graph), 즉 사이클이 없는 유향 그래프에서 꼭짓점들(vertex)을 방향에 거스르지 않고 정렬하는 알고리듬이다. 대학의 선수과목 구조와 같이 순서가 있는 작업들을 나열할 때 이용한다. 위상정렬을 구현하는 방법에는 두 가지가 있는데 하나는 DFS를 이용하는 것이고 다른 하나는 진입차수(indegree)를 이용하는 것이다.

동작 방식

• DFS를 이용하는 방식

1. 그래프에서 방문하지 않은 노드면 DFS를 한다.
2. DFS가 끝나면 해당 노드를 스택에 넣는다.
3. 스택에서 하나씩 꺼내면 위상 정렬된 노드들을 얻을 수 있다.

• 진입차수를 이용하는 방식

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 해당 노드의 자식 노드들의 진입차수를 1 줄인다.
3. 그래프의 모든 노드가 큐에 넣어질 때까지 1 - 2번을 반복한다.
4. 큐에서 하나씩 꺼내면 위상 정렬된 노드들을 얻을 수 있다.

의사 코드

# DFS를 이용하는 방법
def topologicalSort(DAG):
    stk = stack()

    # DFS 신장 트리를 만들어 스택에 넣어준다.
    for v in DAG:
        if v.isVisited == False:
            dfs(v, stk)

    # 위상정렬의 결과는 그래프 순회를 어떻게 하느냐에 따라
    # 여러가지가 될 수 있다.
    return [ stk.pop() for v in stk ]

def dfs(vertice, stk):
    vertice.isVisited = True

    for child in v.children:
        if child.isVisited == False:
            dfs(child, output)

    # 자식 노드에 대한 탐색이 모두 끝나면
    # vertice를 스택에 넣어준다.
    stk.push(vertice)

# 진입차수를 이용하는 방법
def topologicalSort(DAG):
    que = queue()
    result = []

    # 진입차수가 0인 노드를 넣어준다.
    for v in DAG:
        if v.indegree == 0:
            que.push(v)
    
    # 모든 그래프를 순회할 때까지
    while que.empty() == False:
        # 큐에서 노드를 하나 꺼내 result에 넣어준다.
        v = que.pop()
        result.append(v)

        # v의 자식 노드의 진입 차수를 1씩 줄여주고
        for child in v.children:
            child.indegree -= 1
            # child의 진입 차수가 0이 된다면
            # 큐에 넣어준다.
            if child.indegree == 0:
                que.push(child)

    return result