[Python] 위상 정렬(Topology Sort) 알고리즘

https://m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

 

위상 정렬이란

순서가 정해져 있는 작업들을 선행 조건에 만족하도록 정렬하는 알고리즘

정점 u에서 v로 가는 간선이 있을 때 항상 u 다음에 v가 나와야 하는 경우같이 순서가 정해져 있을 때 사용할 수 있다

 

위상 정렬을 쓸 수 있는 경우

-> 그래프가 DAG(방향 비순환 그래프)인 경우

 

순환이 존재하는 그래프에서는 사용할 수 없다

 

+그래프의 종류

https://6mini.github.io/computer%20science/2021/12/02/graph/

[자료구조] 그래프(Graph)란?

방향의 유무

- 방향 그래프(Directed Graphs)

- 비방향 그래프(Undirected Graphs)

순환의 유무

- 순환 그래프(Cyclic Graphs)

- 비순환 그래프(Acyclic Graphs)

 

---

큐를 이용하여 위상정렬 코드로 구현하기

1. 진입 차수(in-degree)를 계산하기 위한 리스트를 정의

2. 진입 차수가 0인 노드를 큐에 추가

3. 큐에서 노드를 꺼내고 결과 리스트에 추가

4. 노드와 연결된 노드들의 진입 차수를 감소 시킨다

5. 진입 차수가 0인 노드를 큐에 추가

3~5 반복

 

모든 노드 처리 후 결과 리스트의 수와 기존 노드의 수가 같다면 위상정렬 완료

아니라면, 순환이 존재

 

from collections import deque

def ts(degree0, graph, indegree):
    q = deque(degree0)
    res = []
    while q:
        v = q.popleft()
        res.append(v)
        for u in graph[v]:
            indegree[u] -= 1
            if indegree[u] == 0:
                q.append(u)
    return res

# 입력: 정점 수(V), 간선 수(E)
V, E = map(int, input().split())
# 그래프와 진입 차수 초기화
graph = [[] for _ in range(V + 1)]
indegree = [0] * (V + 1)

# 그래프 구성 및 진입 차수 계산
for _ in range(E):
    u, v = map(int, input().split())
    graph[u].append(v)
    indegree[v] += 1
        
degree0 = []
for i in range(1, V+1):
    if indegree[i] == 0:
        degree0.append(i)
        
result = ts(degree0, graph, indegree) # 진입 차수가 0인 노드들만
if len(result) == V:
    print(result)
else:
    print("순환이 존재하여 위상 정렬 불가")

 

4 4
1 2
1 3
2 4
3 4
[1, 2, 3, 4]

 

3 3
1 2
2 3
3 1
순환이 존재하여 위상 정렬 불가