[Algorithms/python] 위상 정렬(Topological Sort)

[Algorithms/python] 위상 정렬(Topological Sort)

 

 

 

 

 

• DAG : Directed Acyclic Graph
  • 사이클이 없는 방향 그래프 → 일의 선후 관계 등을 표현할 때 사용하기 용이함
• Topological Sort란
  • DAG에서 그래프의 방향성을 거스르지 않고 정점을 나열하는 정렬방법
• Topological Sort의 방법 : 시간복잡도 : O(V+E)
  • 그래프 그리기, 진입 차수 세기
  • 가장 먼저 진입차수가 0인 노드들 queue에 넣기
  • queue를 돌며 해당 노드와 연결되어 있는 다른 노드들의 진입 차수를 하나씩 낮춰주고, 이 진입 차수가 0이 되었다면 또 queue에 삽입

 

 

 

---

 

 

Directed Acyclic Graph (DAG) : 순환(Cycle)을 가지지 않는 "방향" 그래프

 

 

 

 

위상 정렬(Topology Sort) : DAG에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 것

1. 개념 및 기본 원리

1. 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택
   • 진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방하다.
   • 초기에 간선의 수가 0인 모든 정점을 큐에 삽입
2. 선택된 정점과 여기에 부속된 모든 간선을 삭제
   • 선택된 정점을 큐에서 삭제
   • 선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소
3. 위의 과정을 반복해서 모든 정점이 선택, 삭제되면 알고리즘 종료

 

• 위상 정렬에서는 여러 가지 답이 있을 수 있음 (한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상 있는 경우!)
  • 그래프에서 사이클이 발생할 경우, 그 사이클이 발생한 정점은 감소시킬 수 없는 진입 차수를 갖게 되므로 위상 정렬의 진행이 멈추게 된다.

2. 시간복잡도

• 시간 복잡도는 O(V+E)

 

3. 기본 코드 (BOJ 2252 줄 세우기)

from collections import deque 


N, M = map(int, input().split())

arr = [[] for i in range(N+1)]
in_degree = [0 for i in range(N+1)] # 진입차수

#  A가 학생 B의 앞에 서야 한다 : A->B
def init(a,b):
    arr[a].append(b)
    in_degree[b]+=1

# init
for _ in range(M):
    A,B =  map(int, input().split())
    init(A,B)
    
# print(arr)
# print(in_degree)

# topological sort
def topology_sort():
    result = [] 
    queue = deque()
    # 처음 시작할 떄는 진입 차수가 0인 노드를 먼저 큐에 넣기 
    for i in range(1, N+1):
        if in_degree[i]==0 : # 진입차수가 0이라면 == 리프노드라면 
            queue.append(i)
    
    # 큐가 빌 때까지 
    while queue:
        now = queue.popleft()
        result.append(now)
        print(now, end=' ')
        
        for next_one in arr[now]:
            in_degree[next_one]-=1
            if in_degree[next_one] == 0 : # 새롭게 진입차수가 0이 되는 노드들을 삽입
                queue.append(next_one)

topology_sort()

 

4. 코테 활용

• 위상 정렬은 어떠한 Task들 간의 먼저 이행되어야하는 순서가 존재할 때, 이를 올바른 순서로 진행하기 위해 사용
• 선행 관계 등이 제시될 경우 위상 정렬 문제로 접근할 수 있음

 

 

5. 관련 문제 풀이

 

 

https://github.com/AAISSJ/AlgorithmStudy/tree/main/2024/Data%20Structure/Tree%26Graph/Topology%20Sort

AlgorithmStudy/2024/Data Structure/Tree&Graph/Topology Sort at main · AAISSJ/AlgorithmStudy