위상정렬

위상정렬(Topological Sorting)?

• 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘.
• 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미

 

사용 사례 (ChatGPT 검색..)

1. 작업스케줄링
2. 컴파일러 최적화
3. 의존성 관리
4. 과목 수강신청
5. 일정 계획
6. 네트워크 토폴로지 설계
7.  

위상정렬을 알아가기 위해 진입차수와 진출차수를 알아야 한다.

 

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

 

위상 정렬 알고리즘 동작 과정

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   • 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   • 새롭게 진입차수가 0이 된 노드를 큐에 삽입

-> 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과가 된다.

자세한 동작 과정은 참고 자료 보기..

 

특징

• 사이클이 없는 방향 그래프(DAG: Direct Acyclic Graph)에 대해서만 수행할 수 있다.
• 여러 가지 답이 존재할 수 있다.
• 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다고 판단.
  -> 더이상 진입차수가 0인 정점이 없다는 것.

• 보통 큐로 구현하나, 스택을 이용한 DFS를 이용해 구현 가능.
• 시간복잡도 O(V+E)
  차례대로 모든 노드를 확인하면서(O(V) 해당 노드에서 출발하는 간선을O(E) 차례대로 제거해야 하므로 노드와 간선을 모두 확인하는 것을 고려

 

위상 정렬 알고리즘 코드(Python)

import sys
from collections import deque

input = sys.stdin.readline
# 노드의 개수와 간선의 개수 입력
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트
graph = [[] 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 = []
    q = deque()

    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입차수에서 1빼기
        for g in graph[now]:
            indegree[g] -= 1
            if indegree[g] == 0:
                q.append(g)

    # 위상 정렬 수행한 결과 출력
    for res in result:
        print(res, end=' ')


topology_sort()

# sample input
# 7 8
# 1 2
# 1 5
# 2 3
# 2 6
# 3 4
# 4 7
# 5 6
# 6 4

 

 

출처
https://velog.io/@kimdukbae/%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-Topological-Sorting