[TIL][Tue] 위상정렬 Topological Sorting

학습 자료 (레퍼런스)

https://www.youtube.com/watch?v=xeSz3pROPS8

https://www.geeksforgeeks.org/topological-sorting/

위상정렬

• 그래프 정점의 선형적 정렬(ordering)으로, vertex U에서 V로 가는 방향성이 유지된 채 정렬되는 것. 즉, U가 V를 가리킨다면(향한다면) 위상정렬 시 U는 언제나 V보다 먼저 등장해야 한다. 왜냐하면 U를 거쳐야 V를 갈 수 있기 떄문이다.
• 방향성이 있고 싸이클이 없는 그래프인 DAG(directed acycled graph) 에서만 가능하다.
• 선형 시간 복잡도를 보임 (O(V+E))
• 결과물은 unique하지 않다. (레벨간의 순서 stable은 보장하지만, 결과물이 언제나 동일하지 않다.)
• 이 과업task을 먼저 끝내야 다음을 실행할 수 있는 과업인 선행과업(prerequisites)을 끝내야만 실행되는 업무들, 즉 각자 dependency(의존성)이 있는 업무/과제/과업을 스케쥴링하는 데에 사용된다. ex) 선수과목 수업을 듣기 등의 상황.

주요 개념

• DAG(Directed Acycling Graph)
• 진입계수(indegree)
• 진출계수(outdegree)
• dependecy

왜 중요한가?

의존성을 가지는 task에서 중요하다. 예를 들자면, 파일이 정확한 순서로 컴파일되었는지 보장하는 빌드 시스템, 과업 스케쥴링, 선수과목, job 스케쥴링….

• chat GPT says…
  • Build Systems: Ensuring that source files are compiled in the correct order.
  • Task Scheduling: Executing tasks in parallel while respecting dependencies.
  • Course Prerequisites: Planning the order in which courses should be taken.
  • Job Scheduling: Optimizing the execution of jobs on a computer cluster.

DFS(깊이 우선 탐색 접근)(Stack 사용)

Topological Sorting with examples | Topological Sorting using DFS | Imp For Placements & Comp. Exams

DFS를 recursive하게 접근하여 푼다.

import sys

V, E=list(map(int, sys.stdin.readline().strip().split()))
graph=[[] for _ in range(V+1)]
indegree=[0]*(V+1)
for i in range(E):
    sp, ep=list(map(int, sys.stdin.readline().strip().split()))
    graph[sp].append(ep)

    
def topo_sorting(graph):
    stack=[]
    visited=[False]*(V+1)
    
    #DFS - recursion
    def DFS(vertex):
        visited[vertex]=True
        
        for vtx in graph[vertex]:
            if not visited[vtx]:
                DFS(vtx)
                
        stack.append(vertex)
 
    for vtx in range(1, V):
        if not visited[vtx]:
            DFS(vtx)
    
    #거꾸로 리턴한다.
    return stack[::-1]

print(topo_sorting(graph))

Kahn's Algorithm (Queue 사용)

• 큰 그래프에서 사용하기 유용하다.

from collections import deque
import sys
'''
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
'''

#노드와 간선 받기
V, E=list(map(int, sys.stdin.readline().strip().split()))

####################
# 그레프/테이블 세팅#
####################

#### 그래프 세팅
# 각 노드마다 이 노드에서 향하는 목적지들이 담긴 리스트를 넣을 준비를 한다. 
# [[2,3], [4, 5]...]
# 0 은 안 쓰고 인덱스1부터 써야 하니까 갯수는 V+1로 세팅.
graph=[[] for _ in range(V+1)]

#### 진입 차수 테이블 세팅
#진입차수테이블 세팅 동적으로 값이 바뀌며 
# 진입차수가 0인 것들은 큐에 넣고, 
# 큐에 넣은 그 것들을 불러와 그 노드와 연결된, 
# 그 노드로부터 출발하는 간선을 타고 가 지워 주어야 한다.
indegree=[0]*(V+1)

#edge를 받아 그래프와 진입 차수 테이블에 세팅한다 .
for _ in range(E):
    sp, ep=list(map(int, sys.stdin.readline().strip().split()))
    graph[sp].append(ep) #도착점 삽입
    indegree[ep]+=1 #진입차수를 넣어줌

####################
# 위상정렬 함수 세팅#
####################

def topology_sort(graph, indegree):
    q=deque()
    res=[]

    #진입 차수가 0인 노드를 큐에 삽입 
    #먼저 살펴봐야 하는 노드들.
    for i in range(1, V+1):
        if indegree[i]==0:
            q.append(i) #넣을 때 순서는 상관이 없으니까 append해도 됨.
                
    while q: #큐에 진입 차수가 0인 vertex가 존재하는 동안 반복한다.
        
        now=q.popleft() #현재 작업중인 vertex
        res.append(now)

        for v in graph[now]:
            indegree[v]-=1
            #뺴고 나서 새로 진입 차수가 0이 되면 큐에 삽입
            if indegree[v]==0:
                q.append(v)
    return res

ans=topology_sort(graph, indegree)
print(*ans, sep=',')