위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기서 만약 그래프가 순환을 가진다면 선형 나열은 불가능하다. 아래와 같은 알고리즘은 하나의 방향 비순환 그래프를 위상 정렬 한다. 위상 정렬(G) 1 각 정점 v에 대해 종료 시간 v.f를 계산하기 위해 DFS(G)를 호출한다. 2 각 정점이 종료될 때마다 연결 리스트의 맨 앞에 삽입한다. 3 return 정점의 연결 리스트 중요한것은 위상 정렬한 순서대로 일을 수행할 때 일을 수행하지 못하는 일이 나오지 않는다는 것이다. 미리 어떠한 행동 A를 해야 B를 할 수 있다면 A를 하고 B를 해야한다는 것이다. 위 방식으로 위상 정렬을 할 때 시간복잡도는..
