위상 정렬(topology sort)

📔 위상 정렬(topology sort) 이란

• 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘
• 어떤 일을 하는 순서를 찾는 알고리즘
  • 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것
• 선행 조건이 반드시 수행되어야 다음을 진행할 수 있다!
• 위의 그림을 보면 아비터트리뷰널을 짓기 위해서는 템플러아카이브와 스타게이트가 둘다 있어야 한다.
• 시간복잡도: O(V+E) | V-노드의 수, E-간선의 수

📔 위상 정렬(topology sort) 구현

• 큐와 스택을 사용할 수 있다. 일반적으로 큐를 사용
• 진입 차수( 현재 노드에 들어올 수 있는 노드의 수 ) 가 0인 정점을 큐에 삽입 (그림의 사이버네틱스코어)
• 큐에서 원소를 꺼내 연결된 간선 제거 ( 연결된 간선의 진입 차수를 1씩 빼준다 )
• 이 후 진입 차수가 0이 됐다면 해당 노드를 큐에 삽입
• 여기서 두가지로 나뉜다.
  • 모든 정점을 선택하기전에 큐가 비어있다면 - 싸이클이 존재한다 -> 위상 정렬 불가
  • 모든 정점만큼 수행했다면 -> 큐에서 꺼낸 순서가 위상 정렬의 결과가 된다.

from collections import defaultdict
from collections import deque

V = 7
edges = [
    [1, 2],
    [1, 5],
    [2, 3],
    [3, 4],
    [5, 6],
    [4, 6],
    [6, 7],
]

# 인접 리스트
adj = defaultdict(list)
for edge in edges:
    s, e = edge
    adj[s].append(e)

# print(adj)

# 위상 ( 현재 노드 바로 전 노드가 몇개 인지 ( 나를 지목하고 있는 노드의 개수))
topo = [0] * (V + 1)
for key in adj:
    for node in adj[key]:
        topo[node] += 1

print(f'최초 진입차수: {topo}')

# 진입 차수가 0인 애들을 q에 넣어 준다.
q = deque()
for i in range(1, V + 1):
    if topo[i] == 0:
        q.append(i)

result = []
# 위상 정렬이 완전히 수행되려면 정확히 V개의 노드를 방문해야 한다.
for _ in range(V):
    if not q:
        print('ERROR: 사이클 발생!')
        break

    c = q.popleft()
    result.append(c)
    # c 와 연결 되어있는 간선을 제거 (= 진입차수를 1 뺸다)
    for naver in adj[c]:
        topo[naver] -= 1
        if topo[naver] == 0:
            q.append(naver)

print(f'위상정렬 결과: {result}')

📔 위상 정렬(topology sort) 특징

• 위상 정렬의 순서(Topological Order)가 여러가지 나올 수 있다.
• 위상 정렬 진행 중 남아 있는 정점 중에서 진입 차수가 0인 정점이 없다면 사이클이 존재하는 것으로 위상정렬 알고리즘을 수행할 수 없다.
• DAG(Directed Acyclic Graph) 에만 적용 가능 (즉, 방향이 있는 그래프이고, 싸이클이 존재하면 안된다 )