위상 정렬 (Topological Sort)

목차 위상 정렬 소스 코드 Kahn 알고리즘. DFS 방식.

동작 방식 정리 위상 정렬 (Topological Sort) 位(자리 위): 자리, 위치, 지위 相(서로 상): 서로 관계, 모습, 상태 위상 정렬이란, B는 A 다음에 실행되어야 한다 같은 선행 조건 (의존 관계)이 성립하는 순서로 정렬한다. 한마디로 선행 조건이 있는 작업들을 작업 순서대로 정렬하는 것이다.

예를 들어 게임을 개발하기 위해서 반드시 거쳐야 되는 과정들이 있다. 가장 먼저 핵심 아이디어, 그리고 이를 구체화한 뒤, 개발에 착수해서 테스트 후 게임 출시.

아니면 게임 개발을 외주하여 A부터 Z까지 맡기고, 그렇게 개발이 된 게임을 출시. 어떤 흐름이든, 핵심 아이디어 발상, 또는 게임 기획이 선행 작업으로 존재한다.

위상 정렬은 이러한 흐름을 순차적으로 만드는 알고리즘이다. 이러한 위상 정렬에는 방향성 비순환 그래프 (DAG)라는 조건이 있다.

한마디로 설명하면 그냥 순환하지 않는 그래프만 위상 정렬이 가능...