[알고리즘/개념/그래프] 위상 정렬(Topological Sort)

위상정렬

• 정렬 알고리즘 중 하나로, 순서가 정해져 있는 작업을 차례대로 수행해야 할 때, 사용할 수 있는 알고리즘 입니다.

위상정렬의 현실세계에서의 예시를 들어보겠습니다. 

돈까스를 만든다고 생각을 했을 때, 아래와 같은 순서로 만들 수 있습니다.

1 -> 2 ->4 ->3 ->5 ->6 

일반적으로 생각하면, 튀김재료의 준비는 언제 하든 별로 상관이 없는 행동입니다. 하지만, 튀김 재료가 준비되지 않을 상태에서, 튀김옷을 입혀줄 순 없기 때문에, Node 사이의 관계에서 특정 순서가 정해집니다. 

 

Feedback arc set 과같은 랭킹시스템에 이용이 된다는데, 한번 찾아봐야겠다. 영어로 되어있는 자료밖에 없어서 시간이 좀 걸릴거 같다.

 

위상정렬의 조건

 

위상정렬은 기본적으로, DAG (Directed Acyclic Graph)에서 가능합니다. (사이클이 없는 방향성 그래프)

 

왜 사이클이 형성되면 안되는가 ?

• 간단합니다! 사이클이 형성된다면, 순서를 정할 수가 없습니다. 1->2-3->1의 사이클이라면, 시작점이 어디냐에 따라서, 1,2,3의 우선순위를 따질 수 가 없습니다. 위상정렬은 시작점이 분명 해야합니다.

왜 방향성이 있어야 하는가?

• 방향성이 없다면, 양방향이 되어도 상관이 없다는 이야기인데, 이 또한 위상정렬의 개념에 맞지 않습니다. 위상정렬은 "순서"가 정해져 있는 작업을 차례대로 할때 사용하는데, 애초에 양방향이라면, 순서가 정해져 있지 않다는 이야기 입니다.

위상정렬은 , 하나의 답이 아니라 여러가지의 답이 나올 수 있습니다. 왜냐하면, 위의 예시에서도, 1->2->3->4..순으로 해도되지만, 1->3->2->4..순으로 진행해도 아무런 관계가 없기 때문입니다.

 

위상정렬의 구현

 

위상정렬은 , 진입 차수/진출 차수의 개념을 이용해서 , 구현을 합니다.

 

1. 진입차수가 0인 모든 노드를 큐에 넣습니다.

2. 큐가 빌 때 까지 다음의 과정을 반복합니다

• 큐에서 원소를 꺼내서, 해당 노드에서 나가는 간선을 제거 합니다.
• 새롭게 진입 차수가 0이 된 노드를 큐에 넣습니다.

한 노드를 기준으로, 해당 노드에 들어오는 간선의 갯수를 진입 차수, 해당 노드에서 나가는 간선의 갯수를 진출 차수라고 합니다.

상당히 흥미롭습니다. 진입차수/진출차수의 개념을 이용해서 그래프를 정렬합니다. 

왜 이렇게 될 수 있을까요 ? 직관적으로 생각해봅시다.

 

우선, 처음으로 진입차수가 "0"인 노드들이 큐에 다 추가될겁니다.

이 노드들은, DAG의 시작점이 될겁니다. DAG는 방향성이 정해저있고, 사이클이 없기 때문에, 시작점의 특징은 진입 차수가 없다는 겁니다. 

그리고, 이 노드를 시작점으로, 이제 정해진 순서에 따라 큐에 넣었다가 , 빼면서 해당 노드와 연결된 노드는 다시 넣고, 뺀 값은 result에 저장을 해주면, 큐에 들어간 순서가 정렬된 결과가 나오게 되는 겁니다.

 

코드

import sys
from collections import deque
input =sys.stdin.readline

V,E =map(int,input().split())
graph =[[] for _ in range(V+1)]
indegree=[0 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=[]
    dq=deque()
    for i in range(1,V+1):
        if indegree[i]==0:
            dq.append(i)
    while dq:
        now = dq.popleft()
        result.append(now)
        for nxt in graph[now]:
            indegree[nxt] -=1
            if indegree[nxt] ==0:
                dq.append(nxt)
    for res in result:
        print(res,end=" ")

topology_sort()