간선 (1 -> 3) 이 존재하고 이 간선을 지우게 되면, 3의 InDegree 값이 1만큼 감소해서 2 -> 1로 값이 변하게 됩니다.
InDegree[3]의 값은 0이 아니라서 큐에 집어 넣지 않고, 다음 단계로 넘어갑니다.
[그림 5] 2번 노드와 연결된 간선 지우기
간선 (2 -> 3) 이 존재하고 이 간선을 지우면 3의 InDegree 값이 1 -> 0 으로 값이 변하게 됩니다.
InDegree[3]의 값이 0이라서 큐에 집어 넣습니다.
[그림 6] 3번 노드와 연결된 간선 지우기
간선 (3 -> 4), 간선 (3 -> 5) 를 지웁니다.
4와 5의 InDegree 값이 각각 1씩 감소합니다.
InDegree[4]의 값이 0이라서 4를 큐에 집어 넣습니다.
[그림 7] 4번 노드와 연결된 간선 지우기
간선 (4 -> 5) 의 간선이 제거됩니다.
5의 InDegree 값이 0으로 감소하고 큐에 5를 집어 넣습니다.
[그림 8] 5번 노드와 연결된 간선 지우기
5번 노드와 연결된 간선을 제거합니다.
더 이상 간선이 존재하지 않고, 모든 노드를 살펴보았으므로 위상 정렬을 종료합니다.
위상 정렬 순서는 큐에 담긴 순서입니다.
즉, 1 -> 2 -> 3 -> 4 -> 5 가 됩니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(V + E) 입니다.
V : 노드의 개수
E : 간선의 개수
모든 노드를 하나씩만 확인하기에 O(V) 만큼 걸립니다.
이와 동시에 모든 간선 또한 최대 한 번 확인하기 때문에 O(E) 만큼 걸립니다.
코드
struct TopologicalSort {
int inDegree[SIZE];
void putInDegree(int node) {
++inDegree[node];
}
void solve(int N) {
for (int i = 1; i <= N; i++) {
if (!inDegree[i]) {
queue.enQueue(i);
}
}
while (!queue.empty()) {
int top = queue.deQueue();
printf("%d ", top);
for (int i = 0; i < adj[top].getSize(); i++) {
int next = adj[top][i];
if (!--inDegree[next]) {
queue.enQueue(next);
}
}
}
}
};
사이클이 있을 땐?
위상 정렬은 사이클이 없는 DAG 그래프에서 사용할 수 있다고 위에서 언급했습니다.
그래프에 사이클이 있으면 어떻게 되는 걸까요?
사이클이 있는 그래프에서 위상 정렬을 수행해보겠습니다.
[그림 9] 사이클이 있는 그래프에서 2번 노드까지 위상 정렬을 수행한 모습
위에서 설명한 방식대로 처음에 InDegree가 0인 노드를 찾아서 큐에 넣어주고 시작합니다.
1번 노드, 2번 노드까지 인접한 간선을 제거해보았습니다.
이미 큐에 담겨있는 노드를 제외하고는 inDegree가 0인 노드가 존재하지 않게 됩니다.
그래서 큐에 담기지 않고, 모든 노드를 확인 못한 뒤에 알고리즘이 종료됩니다.
이 방법을 사용하면 그래프에 사이클이 있는지 여부를 쉽게 확인할 수 있습니다.
큐에 들어온 노드의 수 ≠ 노드의 개수 => 사이클이 발생
위의 [그림 9]를 보면 이해가 쉽습니다.
큐에 들어온 노드의 수 = 2
총 노드의 수 = 5
두 숫자가 다르기에 사이클이 있다고 판단할 수 있습니다.
스택과 DFS를 사용
이번엔 진출 차수를 이용합니다.
진출 차수란? 노드에서 나가는 간선의 개수 [그림 10] 모든 노드에 대한 진출 차수
모든 노드가 방문될 때 까지 아래 두 과정을 반복합니다.
임의의 한 노드를 잡고 DFS를 수행합니다.
더 이상 방문할 노드가 존재하지 않는 노드는 스택에 넣습니다.
더 이상 방문할 노드가 존재하지 않는 것을 outDegree 값이 0인지 여부로 확인할 수 있습니다.
하지만 실제로 구현할 때는 outDegree 값을 따로 저장할 필요가 없습니다.
dfs 함수를 수행하면서 현재 노드와 연결된 간선을 전부 확인해봅니다.
연결된 간선을 전부 다 봤다면 해당 노드는 진출 차수가 0이 됩니다.
(간선을 봄과 동시에 해당 간선을 삭제하기 때문입니다.)
즉, dfs 함수 마지막 부분에 stack에 현재 노드를 넣어주면 됩니다.
그림과 함께 자세히 알아보겠습니다.
과정
[그림 11] 1번 노드부터 dfs 시작
임의의 노드 아무거나 두고 dfs를 수행합니다.
저는 1번 노드를 선택했습니다.
[그림 12] 더 이상 간선이 없을 때까지 dfs(1)을 수행한 모습
dfs(1)을 수행하게 되면 연결된 간선을 따라서 dfs(3), dfs(4), dfs(5)를 수행합니다.
[그림 13] 스택에 노드 넣기
더 이상 방문할 노드가 없는 노드부터 스택에 집어 넣습니다.
즉, dfs의 방문 순서 반대로 스택에 집어넣어 주면 됩니다.
[그림 14] dfs(2)를 수행하고 스택에 담긴 모습
이 후에 남은 정점도 dfs를 수행해줍니다.
2번 정점만 남았기에 dfs(2)를 시작합니다.
같은 정점은 더 이상 방문하지 않아도 되기에 dfs(2)만 수행하고 스택에 2번 노드를 담고 종료했습니다.
위상 정렬 순서는 스택에서 pop 한 순서입니다.
2 -> 1 -> 3 -> 4 -> 5
정당성 증명
위의 방법을 귀류법으로 간단하게 증명할 수 있습니다.
[그림 15] 위상 정렬 순서대로 나열한 그림
위의 그림에서 위상 정렬 순서에 반대되는 빨간색 간선 (5 -> 3) 을 그래프에서 추가해 보겠습니다.
dfs(5)에서는 이 함수가 종료되기 전에 간선 (5 -> 3)도 검사합니다.
그럼 visited[3]의 값에 따라서 케이스를 나눌 수 있습니다. (visited[3] : 3번 노드가 dfs를 수행했는지 여부)
visited[3]이 거짓이면,
dfs(5)는 dfs(3)을 호출하게 됩니다.
dfs(3)이 종료된 후에야 dfs(5)가 종료됨으로 이 경우 3은 5보다 왼쪽에 있을 수 없습니다.
visited[3]이 참이면,
dfs(3)은 이미 dfs를 한 번 실행되었다는 소리입니다.
그런데도 dfs(3)이 dfs(5) 보다 늦게 끝났다는 것은 dfs(3)은 현재 스택에 담겨있지 않은, 아직 dfs(3) 함수가 종료되지 않았다는 의미입니다.
dfs(3) -> ... -> dfs(5) -> ... -> dfs(3)
이 경우는 사이클이 되므로 DAG가 아닙니다. 즉, 위상 정렬이 불가능한 조건입니다.
그래서 dfs를 활용한 알고리즘이 정당합니다.
시간 복잡도
이 알고리즘 역시 시간 복잡도는 O(V + E) 입니다.
모든 정점을 한 번만 보기에 O(V) 만큼의 시간이 걸리고,
모든 간선을 한 번만 보기에 O(E) 만큼의 시간이 걸립니다.
코드
struct TopologicalSort {
bool visit[SIZE];
void dfs(int cur) {
visit[cur] = true;
for (int i = 0; i < adj[cur].getSize(); i++) {
int next = adj[cur][i];
if (!visit[next]) {
dfs(next);
}
}
stack.push(cur);
}
void solve(int N) {
stack.init();
for (int i = 1; i <= N; i++) {
if (!visit[i]) dfs(i);
}
while (!stack.empty()) {
int top = stack.pop();
printf("%d ", top);
}
}
};
사이클이 있을 땐?
아까 위에서 귀류법으로 증명을 할 때 사이클에 관해서 얘기를 했습니다.
dfs를 활용한 알고리즘은 SCC 알고리즘을 사용해 사이클을 판별할 수 있습니다.
SCC 알고리즘으로 사이클을 가지는 정점 집합을 추출한 뒤 하나의 노드로 묶어서, 위상 정렬을 수행하면 됩니다.
이에 대한 자세한 설명이 궁금하시다면, 제가 이전에 작성했던 네이버 블로그를 확인해주세요.
