[알고리즘] 위상 정렬

 

위상 정렬💡

- 위상 정렬(Topological sort)는 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것입니다.

- 모든 간선(u,v)에 대해 정점 u가 정점v보다 먼저 오는 순서로 정렬이 됩니다.

 

 

비순환 방향 그래프(DAG)

- 비순환 방향 그래프는 사이클이 없는 방향 그래프입니다.

- 왼쪽 그림과 오른쪽 그림의 차이는 정점2에서의 간선차이입니다. 정점끼리 사이클이 생기면 비순환 방향 그래프가 아니게 됩니다.

 

 

 

위상 정렬 동작 과정

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

 

 

 

1) 모든 정점의 in_degree를 표시합니다.

 

 

2) in_degree가 0인 정점을 큐에 삽입하고 방문표시합니다.

 

3) 큐에서 정점 3을 pop해서 T[]에 append하고 정점 3에 인접한 점들의 in_degree를 감소시킵니다.

 

4) 위의 과정을 반복합니다.

 

5) in_degree의 값이 전부 0 이되고 큐에도 값이 없으면 종료합니다.

 

 

 

위상 정렬 파이썬 코드

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()

 

 

 

Reference

-위상 정렬 : https://yoongrammer.tistory.com/86

위상 정렬(Topological sort) 개념 및 구현