1. 위상정렬
사이클이 없는 방향 그래프에서, 모든 노드에 대해 방향을 거스르지 않으면서, 방향이 특정된 노드 순서대로 나열하는데 활용하는 알고리즘
2. 진입차수와 진출차수
- 진입차수(Indegree) : 특정 노드로 들어오는 간선의 개수
- 진출차수(Outdegree) : 특정 노드에서 나가는 간선의 개수
3. 알고리즘 구현
위상정렬 알고리즘은 DFS를 이용하거나, Queue를 이용하여 구현할 수 있다.
사용 graph는 사이클이 없는 방향그래프(DAG)이고, 진입차수가 0인 노드가 존재해야 적용할 수 있다.
- 진입차수가 최초 0인 노드를 Queue에 넣는다.
- Queue에서 시작노드를 추출하여, 해당 노드의 outdegree에 대해 -1, 즉 이어진 간선을 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 삽입하고, 위 과정을 Queue가 빌 때까지 반복한다.
※ 큐에 들어온 노드의 순서가 위상정렬의 결과이다.
- step 1
최초 진입차수가 0인 노드1을 Queue에 넣는다.
이때 노드1에 인접해있는 노드의 진입차수를 1만큼 뺀다.
- step 2
위에서 갱신한 진입차수를 참조하여, 새롭게 진입차수가 0이된 노드들을 다시 Queue에 넣는다.
- step 3
다시 큐에서 노드들을 추출하면서, 간선을 제거하고 다시 Queue에서 노드들을 추출하는 과정을 Queue가 빌때까지 반복 수행한다.
※위상정렬의 특징을 유의해가며 알고리즘을 구현해본다.
- 큐에서 노드를 추출한 상태에서 진입차수가 0이 아닌 노드가 존재한다면 넘어간다.
- DAG(순환하지않는 방향그래프)에 대해서만 적용이 가능하고, 각 단계마다 Queue에 삽입되는 노드가 2개 이상이라면 답이 여러가지가 될 수 있다.
- 모든 원소를 방문하기 전에 Queue가 빈다면 해당 그래프는 cycling된다고 판단할 수 있고, 더이상 위상정렬을 진행할 수 없게된다.
- stack, DFS를 활용하여 수행할 수도 있다.
- 시간복잡도는 O(V+E)이다.
from collections import deque
import sys
#노드 개수와 간선 개수
v, e = map(int, sys.stdin.readline().split())
#진입차수배열(노드는 1부터 시작)
indegree = [0] * (v+1)
#graph 간선정보
graph = [[] * (v+1) for _ in range(v+1)]
#방향그래프 간선정보(각 노드별 인접노드를 입력받는다)
for _ in range(e):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b) #a > b 통로
indegree[b] = indegree[b] + 1
#위상정렬 수행
def topologySort():
result = []
q = deque()
# 최초 queue에 진입차수가 0인 노드를 삽입
for i in range(1, v+1):
if indegree[i] == 0:
q.append(i)
while q:
now = q.popleft()
result.append(now)
#인접노드
for i in graph[now]:
indegree[i] = indegree[i] - 1
#새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
for i in result:
print(i,end=' ')#결과출력
topologySort()4. 참조자료
이코테 2021 - 위상정렬
https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8
