Topological Sort (위상정렬) 알고리즘 개념 정리 및 활용 방법 (python)

Topological Sort란?

- 순서가 정해져 있는 작업 처리해야 할 때 (선후 관계가 정해진 작업)

- Direct Graph의 모든 노드를 방향성에 거스르지 않고 순서대로 나열하는 것

- 조건 : DAG(Directed Acyclic Graph), 즉 방향이 존재하고 사이클이 없는 그래프여야 함.

 

Topological Sort 구현 방법

1. DFS 이용한 Topological Sort

- dfs를 그대로 적용하되 하나의 동작만 추가하면 끝

- 더 이상 이동할 노드 없으면 list에 추가 (재귀함수의 dfs에서 이웃 노드들 dfs호출한 뒤 for 문 뒤에 추가하면 됨)

import sys
from collections import deque 
sys.setrecursionlimit(10 ** 6) 
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

neighbor=[[] for _ in range(n+1)]

# 1. 인접 리스트 생성 
for a,b in edges: 
    neighbor[a].append(b)

# 2. DFS 진행 
visited=[0]*(n+1)
order =[]
def dfs(node):
    visited[node]=1
    for neigh in neighbor[node]:
        if not visited[neigh]:
            dfs(neigh)
    order.append(node)

for i in range(1,n+1):
    if not visited[i]:
        dfs(i)

# 3. 생성한 list의 역순으로 출력
for i in order[::-1]:
    print(i,end=" ")

 

2. In-Degree 이용한 Topological Sort

- In-degree : 현재 노드를 기준으로 몇 개의 노드가 들어오는지 (내 앞에 먼저 처리되어야 할 작업의 개수)

- in-degree가 0인 노드들을 전부 deque에 넣어주고 deque이 빌 때까지 진행 

- deque에서 노드 하나 꺼내고 해당 노드의 이웃노드들을 순회하며 각 이웃노드들의 in-degree값을 1씩 빼준다 

- 이 과정에서, 이웃 노드의 in-degree가 0이 된다면 deque에 넣어주기 (0이 됐다는 것은 사전에 처리해야 할 작업이 다 끝났다는 것)

import sys
from collections import deque 
sys.setrecursionlimit(10 ** 6)
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

neighbor=[[] for _ in range(n+1)]

pq=deque()
indegree=[0]*(n+1)

# 1. 인접 리스트 생성 & indegree 계산 
for a,b in edges: 
    neighbor[a].append(b)
    indegree[b]+=1 

# 2. indegree가 0인 노드들 deque에 추가
for i in range(1,n+1): 
    if indegree[i]==0: 
        pq.append(i)

# 3. deque에서 값 하나씩 꺼내서 업데이트
while pq:
    node=pq.popleft()
    print(node,end=" ") # deque에서 하나씩 꺼내며 바로 출력
    # 이웃노드들의 indegree -1 
    for neigh in neighbor[node]:
        indegree[neigh]-=1 
        if indegree[neigh]==0: 
            pq.append(neigh)

 

=> 만약 모든 노드를 방문하기 전에 deque(queue)가 비었다는 것은 사이클이 존재한다는 것 

 

 

 

"즉, '위상정렬'을 통해 그래프에 사이클이 존재하는지 판단할 수 있습니다"

 

Topological Sort 이용해 그래프의 사이클 확인하기

[In-Degree 이용해 위상정렬을 할 경우]

1. deque에서 노드를 꺼내서 이웃노드를 살피는데 이웃노드의 in-degree가 0인 경우

2. 위상정렬을 모두 했는데(deque이 비어서 while 끝남) deque에 들어간 노드의 개수가 전체 노드의 개수보다 적을 때 

 

from collections import deque
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

neighbor=[[] for _ in range(n+1) ] 
indegree=[0]*(n+1)
cons=True # 사이클이 있는지 (위상정렬에 모순이 있는지) 확인하는 flag. 있으면 False로 변환

for a,b in edges: 
    neighbor[a].append(b)
    indegree[b]+=1 

pq=deque()
pq_cnt=0 # 모든 노드가 deque에 들어간 경험이 있는지 count 
for i in range(1,n+1):
    if indegree[i]==0: 
        pq.append(i)
        pq_cnt+=1 

while pq:
    node=pq.popleft()
    for neigh in neighbor[node]:
        if indegree[neigh]==0: # 이웃노드에서 indegree를 1 빼야하는데 이미 0인 경우
            cons=False
            break 
        indegree[neigh]-=1 
        if indegree[neigh]==0: 
            pq.append(neigh)
            pq_cnt+=1  # deque에 넣을 때 count+=1

    if not cons: break 

if pq_cnt!=n: cons=False # 모든 노드가 deque에 들어가지 않은 경우

if cons : print("Consistent")
else: print("Inconsistent")

 

 

사전 순대로 Topological Sort 하는 법

한 그래프에 대해 위상정렬을 할 때 하나의 방법만 존재하는 것은 아닙니다. 

(gemini로 제작)

해당 예시만 봐도 1->2->3->4->5 도 가능하고, 1->3->2->4->5 도 가능합니다. 

이런 경우 위상정렬을 '사전순대로 혹은 노드 번호가 작은수대로' 하기 위해선 어떻게 해야할까요?

- In-degree 방법에서 노드들을 넣고 빼준 deque을 대신해 priority queue를 사용하면 됩니다. priority queue는 넣은 순서를 유지하는 deque과 달리 자동으로 queue안에 있는 값을 정렬해줍니다. 

import heapq #python에선 priority queue를 하기 위해 heapq 사용
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

adjacent=[[] for _ in range(n+1)]
indegree=[0]*(n+1)
for a,b in edges:
    adjacent[a].append(b)
    indegree[b]+=1 

pq=[]
for i in range(1,n+1):
    if indegree[i]==0:
        heapq.heappush(pq, i)

while pq:
    node=heapq.heappop(pq)
    print(node,end=" ")
    for neigh in adjacent[node]:
        indegree[neigh]-=1
        if indegree[neigh]==0:
            heapq.heappush(pq,neigh)

 

Topological Sort의 시간복잡도 / 공간복잡도

1. 시간 복잡도 : O(V+E)

- V(노드 개수), E(엣지 개수). 

- 진입차수(In-Degree) 계산 : O(E)

- Queue 초기화 : 모든 노드를 확인하며 진입차수가 0인 노드 찾기 O(V)

- 노드 방문 & In-Degree 계산 : O(V) , O(E) => O(V+E)

2. 공간 복잡도 : O(V+E)

- 인접 리스트 : O(V+E)

- In-degree 배열 : O(V)

- Queue : 최악의 경우 모든 정점이 한번에 존재 : O(V)

- 결과 리스트 : O(V)

=> O(V+E)