TIL : 위상정렬 알고리즘 (21)

💻 알고리즘

📌 위상정렬 알고리즘

Cycle이 없는 방향 그래프에서 작업 순서를 구하는 알고리즘이다.

이전에 공부한 적 있으나 기록을 남겨두지 않아서 남겨두려고 한다.

💡 특징

• 순환하지 않는 방향 그래프에서만 가능하다.
• 진입 차수 (in-degree) 또는 진출 차수 (out-degree)를 이용한다.
• 여러 개의 답이 존재할 수 있다
• O(V+E)의 시간 복잡도를 가진다.

💡 동작 원리 (진입차수 ver)

• 진입 차수가 0인 정점을 큐에 넣는다.
• 큐에서 원소를 꺼내 연결된 간선을 제거한다.
• 진입 차수가 0이라면 해당 정점을 큐에 삽입한다.
• 마지막에 Cycle의 존재 유무를 확인한다. 결과의 크기가 정점의 개수보다 작다면 Cycle이 존재하는 것이다.

from collections import deque

def topologySort():
    result = []
    q = deque()
    
    for i in range(SIZE):
        if inDegree[i] == 0:
            q.append(i)
    
    while q:
        v = q.popleft()
        result.append(v)
        
        for i in graph[v]:
            inDegree[i] -= 1
            if inDegree[i] == 0:
                q.append(i)
                
    if result == SIZE: # 사이클 확인
        return result

💡 동작 원리 (진출차수 ver)

• 임의의 정점에서 DFS를 수행한다.
• 특정 정점에서 더 이상 방문할 곳이 없다면 스택에 담는다.
• 모든 정점을 방문했으면 스택을 반환한다.
• 중간에 Cycle을 확인한다. 방문 표시가 되어있는데 아직 끝나지 않았다면 그게 바로 Cycle이다.

def dfs(i, stack, visited):
    visited[i] = True
    
    for i in graph[i]:
        if not visited[i]:
            dfs(i, stack, visited)
            
    stack.append(i)

def topologySort(start):
    result = []
    stack, visited = [], [False] * SIZE
    stack.append(start)

    for i in range(SIZE):
        if not visited[i]:
            dfs(i, stack, visited)
    
    while stack:
        v = stack.pop()
        result.append(v)
            
    return result