Topological Sorting

smsh0722·2022년 4월 24일
0

Graph

목록 보기
3/20

Topological Sorting은 여러 가지 일들에 순서가 있을 때, 그 순서를 거스르지 않도록 일을 나열하는 것을 말한다.

각 일들을 nodes로 보면 일종의 Directed Graph로 볼 수 있다. 이때, Cycle이 있다면 순서를 거스르지 않는 것이 불가능하기 때문에, Directed Acyclic Graph(DAG)이어야 한다.

Algorithm 1

간단하게, DFS를 조금 수정하면 다음과 같이 Topological Sorting을 할 수 있다.

1. 현재 node와 인접한 방문하지 않은 nodes로 Recursive Call을 한다.
2. recursive call이 모두 끝나면, 현재 node를 stack에 추가한다.
3. DFS가 모두 완료되면, Stack을 출력한다.

여기서 중요한 점은, 인접 nodes에 대한 recursive call이 모두 끝나고 현재 node를 stack에 push 한다는 점이다.

시간 복잡도는, DFS만 하면 끝나기 때문에 O(V+E) 이다.

Algorithm 2

Khan's Algorithm이라고도 불리는 두 번째 방법은, indegree가 0인 것부터 순차적으로 빼면서 선행 nodes가 없거나 이미 빠진 nodes를 빼는 방법이다.

1. 모든 nodes의 indegree를 계산한다.
2. indegree가 0인 nodes를 Queue에 추가한다.
3. Queue에서 node 하나를 꺼낸다.
    - 해당 node와 인접한 nodes의 indegree를 1씩 줄인다.
    - 만약 인접 nodes의 indegree가 0이 됐다면 Queue에 추가한다.
4. Queue가 빌 때까지 3을 반복한다.
5. Queue에서 꺼낸 이 순서가 곧 Topological order이다.

시간 복잡도는 마찬가지로 O(V+E)이다.

profile
Military service - May 31, 2022 ~ Nov. 30, 2023

0개의 댓글