[알고리즘] 위상 정렬

위상 정렬

• 방향 그래프에서 간선으로 정점 간 선후관계가 주어졌을 때, 선후관계가 위배되지 않도록 나열하는 정렬
• 하나의 그래프에 여러 개의 위상 정렬 결과가 있을 수 있음
• 그래프 내에 사이클이 없어야 위상 정렬이 만들어질 수 있음 (사이클이 없는 방향 그래프: DAG(Directed Acyclic Graph)
• 위상 정렬의 시간 복잡도는 O(V+E) -> 모든 정점을 큐에서 한 번씩 꺼내면서 연결된 간선을 제거함 O(V) + 각 간선을 한 번씩 탐색하면서 진입 차수를 감소시킴 O(E) -> 빠른 속도의 알고리즘

구현 방법

위상 정렬을 코드로 구현할 때 매번 정점과 간선을 지우면 매번 O(V^2)로 동작하게 될 것이다.

대신 미리 indegree 값을 저장해뒀다가 매번 indegree값을 1씩 감소시키는 방법을 사용하면 된다.

또는 indegree가 0인 정점을 다 확인하는 게 아니라 목록을 큐에 따로 저장해뒀다가 직전에 제거한 정점에서 연결된 정점들만 추가하는 방법을 사용할 수도 있다.

 

1. 진입 차수가 0인 노드를 큐에 다 넣기
2. 큐에서 노드를 꺼내 해당 노드에서 출발하는 간선들의 진입 차수를 1씩 감소
3. 새롭게 진입 차수가 0이 된 노드들을 큐에 넣기
4. 1~3 과정을 큐가 빌 때까지 반복

이 과정이 끝나고 난 후 만들어진 트리에 모든 노드가 포함되지 않았다면 사이클이 있다는 의미

사이클이 존재하게 되면 진입 차수가 0이 될 수 없기 때문에 사이클에 해당하는 어떤 원소도 큐에 들어갈 수 없기 때문

 

즉, 사이클이 판별된 순간부터 큐에 더 이상 노드가 들어가지 않음

위상 정렬에서 가장 앞에 오는 정점 -> 자신으로 향하는 간선이 없어야 함 (indegree가 0이어야 함)

구현하기

indegree가 0인 정점은 A, C, G이므로 이 원소들이 위상 정렬 시 가장 앞에 올 수 있음

임의의 노드로 A를 선택하였음

위상 정렬에 A를 추가한 뒤로는 A에서 다른 정점으로 나가는 간선이 의미 없어짐

왜냐하면 A가 이미 먼저 나온 게 확정된 상태기 때문에 A에서 나가는 정점은 무조건 A 뒤에 오게 되어있음

따라서 A와 A에서 나가는 간선들을 모두 지운 후 위상 정렬을 이어나가면 됨

그러면 또 맨 앞에 올 수 있는 노드는 C, G가 되는데 임의로 C를 선택했음

C와 C에서 나가는 간선들을 모두 지움

마찬가지로 D를 선택한 후 D와 D에서 나가는 간선들을 모두 지움

끝까지 수행하면 ACDGEBF라는 결과를 얻을 수 있음

사이클이 존재하지 않는 방향 그래프에서는 해당 알고리즘이 늘 올바른 위상 정렬 결과를 만든다.

 

파이썬 코드:

from collections import deque

v, e = map(int, input().split())
indegree = [0]*(v+1)
graph = [[] for _ in range(v+1)]
for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

def topology_sort():
    result = []
    q = deque()
    for i in range(1, v+1): # O(V)
        if indegree[i] == 0:
            q.append(i)
    while q:
        node = q.popleft()
        result.append(node)
        for next in graph[node]: # O(E)
            indegree[next]-=1
            if indegree[next]==0:
                q.append(next)

    for i in result:
        print(i, end=' ')

topology_sort()

 

ref:

https://techblog-history-younghunjo1.tistory.com/264

[Python] 노드 간의 선후 관계를 고려하는 위상(Topology) 정렬 알고리즘

 

https://blog.encrypted.gg/1020

[실전 알고리즘] 0x1A강 - 위상 정렬