위상 정렬 (Topological Sorting)

위상 정렬이란?

위상 정렬은 그래프 알고리즘 중 DAG(Directed Acyclic Graph), 즉 방향성이 있으면서 싸이클이 없는 그래프에서 정점들을 순서대로 정렬하는 방법이다.

 

 

위상 정렬은 다음과 같은 상황에서 유용하다.

- 작업 스케쥴링
- 선수 과목에 대한 문제
- 데이터 처리 파이프라인

 

---

위상 정렬의 조건

위상 정렬을 사용하기 위해선 위에서 언급한 것처럼

1. edge(간선) 에 방향이 있어야 한다.

2. 비순환 그래프 즉, 싸이클이 없어야 한다.

 

이 두가지 조건을 만족해야 한다.

 

위상 정렬은 큐 기반 위상 정렬과 dfs 기반 위상 정렬로 나뉜다.

두 방식에 대해 각각 알아보자.

---

큐 기반 위상정렬

큐 기반 위상정렬은 다음과 같은 단계를 따른다.

1.
각 정점의 진입 차수(inDegree)를 계산한다.

2.
진입 차수가 0인 정점을 큐에 삽입한다.

3.
큐에서 정점을 하나씩 꺼내면서 해당 정점에서 나가는 간선을 제거한다.
간선을 제거하며 새롭게 진입 차수가 0이 되는 정점을 큐에 삽입한다.

4.
큐가 빌 때까지 이를 반복한다.

 

<예시 코드>

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void topologicalSort(int V, vector<vector<int>>& adj) {
    vector<int> indegree(V, 0); // 각 정점의 진입 차수 계산
    for (int u = 0; u < V; u++) {
        for (int v : adj[u]) {
            indegree[v]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < V; i++) {
        if (indegree[i] == 0) q.push(i); // 진입 차수가 0인 정점을 큐에 추가
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " "; // 정렬된 순서 출력

        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) q.push(v); // 새롭게 진입 차수가 0이 된 정점 추가
        }
    }
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);

    adj[5].push_back(2);
    adj[5].push_back(0);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);

    topologicalSort(V, adj);
    return 0;
}

---

DFS기반 위상정렬

dfs기반 위상정렬은 다음과 같은 단계를 따른다.

1.
모든 정점에 대해 dfs를 수행한다.

2.
탐색이 끝나는 순서대로 정점을 스택에 추가한다.

3.
스택에 저장된 순서대로 정점을 출력한다.

 

<예시 코드>

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void dfs(int u, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& s) {
    visited[u] = true; // 현재 정점 방문 처리
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v, adj, visited, s); // 이웃 정점 방문
    }
    s.push(u); // 방문이 끝난 정점을 스택에 추가
}

void topologicalSort(int V, vector<vector<int>>& adj) {
    vector<bool> visited(V, false); // 방문 여부 체크
    stack<int> s;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) dfs(i, adj, visited, s); // 방문하지 않은 정점에 대해 DFS 수행
    }

    while (!s.empty()) {
        cout << s.top() << " "; // 스택에서 정점을 꺼내며 출력
        s.pop();
    }
}

int main() {
    int V = 6;
    vector<vector<int>> adj(V);

    adj[5].push_back(2);
    adj[5].push_back(0);
    adj[4].push_back(0);
    adj[4].push_back(1);
    adj[2].push_back(3);
    adj[3].push_back(1);

    topologicalSort(V, adj);
    return 0;
}

 

---

큐 기반  vs  DFS기반

장점

큐 기반
-간단하고 효율적
-O(V+E)의 시간 복잡도를 가진다
-노드의 순서를 점진석으로 생성해 사용하기 쉽다.


DFS 기반
-재귀적으로 동작하여 구현이 간결하다.
-그래프를 탐색하면서 동시에 위상정렬을 수행할 수 있다.

 

단점

큐 기반
-진입 차수를 계산할 추가적인 메모리가 필요하다.
-순서를 생성하는 과정이 재귀에 비해 직관적이지 않을 수 있음.


DFS 기반
-재귀 호출 스택이 추가적으로 필요함.
-순서 생성 과정이 명시적이지 않아 DFS종료 후에만 결과를 알 수 있음

 

위의 장단점에 따라,

큐 기반 위상정렬은 작업 스케쥴링과 같은 간단한 순서 계산에 적합하고,

DFS 기반 위상정렬은 그래프 분석 작업이나 탐색과 동시에 위상 정렬이 필요한 경우에 적합하다.

 

 

위상 정렬의 결과는 유일하지 않을 수 있으니 유의해야 한다.