위상정렬(topological sorting)

[알고리즘] 위상정렬(topological sorting)

위상정렬은 그래프를 자료구조로 가지는 알고리즘으로 유향 그래프의 정점들을 한 방향으로 나열하는 것을 말한다. 예를 들어 김치찌개를 만드는 방법을 입력받았을 때 그것을 하나의 순서로 만드는 것이다. 여러 가지 순서를 가질 수 있으며, 특정 조건에 따라 우선순위 큐(priority queue)를 사용할 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 하며 이러한 그래프를 비순환 유향 그래프라고 한다. 위상정렬을 구현하는데 여러 방법을 쓰일 수 있는데, 나는 여기서 큐와 진입 차수(indegree)를 이용한 방법을 설명하려고 한다.

알고리즘 순서는 다음과 같다.

1. 간선 정보를 초기화한다. 이 때, 문제에 따라 인접행렬, 인접리스트 중 선택해서 구현할 수 있다.

2. 진입차수의 정보를 0으로 초기화 한다.

3. 유향 그래프를 생성한다. 이 때 u->v라고 하면 v의 진입차수를 1 증가시킨다.

4. 진입차수가 0인 것을 큐에 삽입한다.

5. 큐 순서대로 진행이 되며, 해당 정점과 연결되어 있는 정점의 진입차수를 1 감소시킨다. 이 과정으로 인해 진입차수가 0이 된다면 다시 큐에 삽입한다.

6. 큐가 빌 때까지 반복한다.

7. 큐가 비었을 때, 진입차수를 확인한다. 만약 0이 아닌 정점이 존재한다면 다음 그래프는 순환(cycle)이 존재한다는 뜻이므로 정렬이 불가능하다. 아니라면 큐에서 삭제한 순서대로 정렬된 것이다.

의사 코드(qseudo code)

/* N: 정점의 개수 */ for i = 0 to N for j = 0 to N adj[i][j] = false //인접행렬 초기화 for i = 0 to N indegree[i] = 0 //진입차수를 0으로 초기화 for i = 0 to N for j = 0 to N if (i, j) is connected adj[i][j] = true indegree[i] = indegree[i] + 1 for i = 0 to N if indegree of i is zero push queue while until queue is empty for i = 0 to N if front of queue is connected with i indegree[i] = indegree[i] - 1 if indegree of i is zero push queue for i = 0 to N if indegree of i is not zero this can not sort

시간복잡도는 인접행렬과 인접리스트에 따라 다르지만 O(N^2)이다.

정점의 수보다 간선의 수가 더 많다면 인접행렬을, 정점의 수에 비해 간선의 수가 적다면 인접리스트를 사용하는게 좋다.