🎢 Topology Sort

intro

🎢 위상 정렬 = 사이클이 없는 방향 그래프(DAG; Directed Acyclic Graph)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

→ 위상 정렬은 DAG에 대해서만 수행할 수 있다

→ 여러 가지 답이 존재할 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우(문제에서 오름차순, 내림차순 명시 없다면) 여러 가지 위상정렬 노드 결과가 존재 가능

→ 모든 원소를 방문하기 전에 queue가 빈다면 사이클이 존재한다고 판단 가능(사이클에 포함된 원소 중에서 어떠한 원소도 queue에 들어가지 못한다) (또는 queue에서 노드를 뽑을 때마다 뽑은 노드의 개수가 카운트 되어서, 최종 카운트 된 노드의 개수와 그래프 전체 노드의 개수가 같은 지 다른 지 비교로도 알 수 있음)

→ 스택을 활용한 DFS를 이용해 위상 정렬 수행도 가능

 

🎢 위상정렬 시간 복잡도: O(V+E)로 간선과 노드의 개수가 전체 시간복잡도. 각각 노드와 간선을 한 번씩 확인하기 때문이다.

 

🎢 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수 / 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수

BFS topology sorting

※ BFS의 queue 자료구조 사용

① 진입차수(Indegree)가 0인 모든 노드를 queue에 넣는다.

 

② queue가 빌 때까지 아래 2가지 과정을 반복한다.

② - 1. queue에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다(indegree 값을 1씩 감소)

② - 2. 새롭게 진입차수가 0이 된 노드를 queue에 넣는다.

 

③ 결과적으로 각 노드가 queue에 들어온 순서가 위상 정렬을 수행한 결과와 같다.

 

※ 예시) 그래프는 DAG(사이클이 없는 방향 그래프)로 준비되어야 한다. 사이클이 포함되어 있는 그래프라면, 사이클이 포함되어 있는 모든 노드는 진입차수가 1 이상이 된다.

① Directed Acyclic Graph 준비

② 진입차수(indegree)가 0인 노드 1 queue에 넣기

③ 노드 1을 queue에 꺼내고, 노드 1에서 나가는 간선(outdegree 개수 만큼) 제거

④ 새롭게 진입차수가 0이 된 노드 2와 노드 5 queue에 삽입

④ 동일 방법으로 노드 2를 빼서 노드 2에서 나가는 간선을 제거 / 그리고 새롭게 진입차수가 0이 된 노드 3 queue에 삽입

④ 그 다음 노드 5를 빼서 동일 방법으로 노드 6을 queue에 삽입

④ 그 다음 노드 3을 빼고, 이후 진입차수가 0이 된 노드는 없으므로 그대로 유지

④ 노드 6을 빼고, 동일 방법으로 노드 4를 queue에 삽입

④ 노드 4를 빼고, 동일 방법으로 노드 7을 queue에 삽입

④ 노드 7을 꺼냄.

∴ 위상 정렬 결과) queue에 삽입된 전체 노드 순서: 1 → 2 → 5 → 3 → 6 → 4 → 7

code

from collections import deque

v, e = map(int,input().split()) #number of vertices, number of edges
indegree = [0] * (v+1) #initialize it to 0 in all each nodes
graph = [[] for i in range(v+1)] #graph initialization

for _ in range(e): #in each edges
    a,b = map(int,input().split()) #node a -> node b
    graph[a].append(b)
    indegree[b] += 1

def topology_sort():
    result = []
    q = deque()
    
    #1. insert nodes in a queue having zero indegrees
    for i in range(1,v+1):
        if indegree[i] == 0:
            q.append(i)

    #2. repeat until emptying the queue
    while q:
        node = q.popleft()
        result.append(node) #update result list
        for i in graph[node]:
            indegree[i] -= 1 #remove edges
            if indegree[i] == 0: #insert nodes having 0 indegree
                q.append(i)
    for i in result:
        print(i,end=' ')

topology_sort() #1 2 5 3 6 4 7
'''
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
'''

examples

★ <BOJ G3 2252 줄 세우기> ★

: A가 B 앞에 서야 하는, 순서가 정해진 데이터는 노드 A → 노드 B의 연결을 누적으로 만든, 위상정렬 결과 최종 출력. 위상정렬 기본 문제

 

★ <BOJ G3 2623 음악프로그램> ★

: 2252와 동일한 위상정렬 교과서 문제. 다만, A -> B -> C와 같이 두 개 이상의 연결된 node 순서가 정해진 문제. 이 때 graph와 indegree update만 잘 설정해주면 끝. 첫번째 node부터 맨 끝 바로 앞의 node까지만 graph update / indegree는 그 반대로 두번째 node부터 맨 끝 node까지의 모든 node의 indegree -=1로 update

 

★ <Leetcode Medium 207. Course Schedule> ★

: (index 0부터 시작 주의) b를 선수강하고 a를 수강(b → a) acyclic graph만 위상정렬이 가능하므로, 모든 courses(노드)를 끝낼 수 있는지, 즉, 위상정렬이 가능한지(=사이클이 존재하지 않는 지) 묻는 문제. 사이클 존재 유무 판별은, queue에서 뺀 노드의 개수를 계속 세고, 최종 센 노드의 개수와 그래프 전체 노드의 개수가 서로 같은 지 다른 지 비교하면 된다.

 

★ <Leetcode Medium 210. Course Schedule II> ★

: 위 207 위상정렬의 연장선 문제. 직접 topology sort 내용을 출력하는 문제.