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

위상

- 항목 간의 상대적인 위치나 순서를 의미 (컴퓨터 과학에서의 특별한 의미)

- 즉, 어떤 노드(작업, 과목 등)가 다른 노드보다 먼저 와야 하는지, 또는 먼저 수행되어야 하는지에 대한 순서의 구조(structure)를 뜻함.

위상 정렬

- 방향 그래프에서 노드들 간의 선후 관계(의존성)를 고려해 순서를 정렬하는 것

- DAG(Directed Acyclic Graph)에만 적용이 가능하다. (사이클이 발생하는 경우 위상 정렬을 수행할 수 없다)

위상 정렬 알고리즘 특징

1. 현재 그래프는 위상 정렬이 가능하지

2. 위상 정렬이 가능하다면 그 결과는 무엇인지

위상 정렬 수행 알고리즘 설명

1. 진입차수가 0인 정점을 큐에 삽입합니다.

2. 큐에서 원소를 꺼내 열결된 모든 간선을 제거합니다.

3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입합니다.

4. 큐가 빌 때까지 2~3번 과정을 반복합니다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과입니다.

Python기반 알고리즘 구현

from collections import defaultdict, deque

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * numCourses
    
    # 그래프와 진입 차수 초기화
    for a, b in prerequisites:
        graph[b].append(a)
        indegree[a] += 1

    # 진입 차수가 0인 노드부터 큐에 넣기
    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    completed = 0

    while queue:
        course = queue.popleft()
        completed += 1
        for neighbor in graph[course]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return completed == numCourses

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