[그래프 알고리즘]위상정렬

DAG Directed Acyclic Graph

DAG는 사이클이 없는 방향 그래프를 의미합니다.

나가는 엣지만 있고 들어오는 엣지가 없는 노드를 선택하여 DFS 순회하면 모든 노드를 방문할 수 있습니다.

위상정렬 Topological Sort

위상정렬이란 DAG인 그래프의 노드를 어떤 순서대로 나열하는 것으로,

위상정렬된 그래프의 노드열에서는 뒤에 오는 노드에서 앞에 노드로 가는 경로는 존재하지 않습니다.

한 DAG의 위상 정렬 결과는 여러개일 수 있습니다.

위상정렬된 노드들을 2차원 평면에 놓는다면, 엣지들을 왼쪽에서 오른쪽으로만 향하게 할 수 있습니다.

DFS로 구현

위상정렬은 DFS로 간단하게 구현됩니다.

한 노드에서 연결된 다른 노드들을 모두 순회하고, 자신의 노드 번호를 리스트에 넣으면 됩니다.

그러면 그 리스트에는 위상정렬의 역순으로 노드들의 번호가 저장되어 있으므로, 이를 뒤집으면 위상정렬된 노드들의 번호가 됩니다.