Topological Sort(위상 정렬)

 

1. 개념

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(directed acyclic graph)여야 한다.

유향 그래프 - 위키백과, 우리 모두의 백과사전

기본 개념은 위키백과 참조

 

[용도]

어떤 일의 순서를 결정하는 것으로

• 산업공학과에서 공장 생산 순서 프로세스
• 선수, 후수과목 수강신청 프로세스 등에 활용된다.
• 또, 알고리즘 특성상 DAG (사이클이 존재하지 않는 유방향 그래프)에서만 동작하므로 사이클 존재 유무 판단에도 활용된다.

 

 

2. 알고리즘

Input	DAG (Directed Acyclic Graph)
Output	ordred Graph ( vertex[i] => vertex[j] (i < j))

※ There is no Back Edge, Cycle!

 

based BFS Traversal

① Indegree가 0인 노드를 찾아 Queue에 추가한다.

② 방금 찾은 노드의 인접 노드 Indegree를 모두 -1 한다.

③ Queue 가 비어있을 때 까지 다시 Indegree가 0인 노드를 pop하여를 1, 2를 반복한다.

 

⭐ 위상 정렬 순서는 여러개가 나올 수 있으며
  모든 노드를 찾기 전에 Queue가 비어있으면 DAG (Directed Acyclic Graph)가 아니다. == 사이클이 존재한다.

 

based DFS Traversal

① Indegree가 0인 Node를 찾아 Queue에 추가한다.

② Parent -> Child Node중 Indegree 0인 노드를 Queue에 추가하며

해당 child Node의 Indegree +1 한다.

③ Parent Node였던 Node를 연결되었던 Edge도 해제하며 Queue에서 Pop한다.

(이 때 자동으로 Indegree Update가 이루어진다)

※ 연결되었던 Edge가 해제되어도 + 별도의 Stack을 사용하지않아도

자손노드는 Code Flow에서 어차피 부모로 돌아가게 된다.

Recursive Call을하면 더 이상 연결된 Edge가 없을 때

Code Flow상 Parent Node로 돌아오기 때문이다.

 

④ Indegree Update하며 ①~③을 반복한다. (모든 Queue가 비어있을 때 까지)

 

Stack, BFS를 통해 구현하는 것도 물론 가능하다.

 

3. Cycle Check

 

위 그림에서 Vertex 2번 4번은 Back Edge가 없을 수 밖에 없다.

알고리즘 구조상 Indegree가 0이여야만 추가, 출력되는데

Back Edge(Cycle 형성 원인)가 있다면 Indegre ≠ 0 때문에 추가되지 않았을 것이기 때문에 모순이다.

∴ DAG, Topological Sort에서 cycle & Back Edge는 존재하지 않는다.

    

 

<명제> Indegree = 0 인 Node가 반드시 1개 존재한다.

(귀류법 증명) 모든 노드의 Indegree가 0이 아니면 

반드시 1개 이상의 BackEdge가 존재하게 되므로 cycle이 발생 

-> Topological sort Input은 DAG이므로 cycle 발생시 Topological Sort 불가능.

∴ Topological Sort or DAG에는 반드시 Indgree = 0 인 노드가 존재한다.

4. Time Complexity

O(N+M)

 

DFS 수행하면서 Indegree 계산 후

Indegree 0 인놈만 출력하며 출력된 node, edge를 지우고

Indegree update가 이루어지는 방식이므로

DFS를 2회 실행한 것과 비슷한 시간 복잡도를 가진다.