위상 정렬(Topological Sorting)은 방향성 비순환 그래프(DAG, Directed Acyclic Graph)의 정점들을 선형 순서로 배열하는 기법으로, 모든 방향 간선 u → v에 대해 정점 u가 반드시 정점 v보다 앞에 오도록 정렬합니다. 만약 그래프가 DAG가 아니라면, 즉 사이클이 존재한다면 해당 그래프에 대한 위상 정렬은 불가능합니다.
함수 구성 및 의사코드
이 프로그램은 깊이 우선 탐색(DFS)을 재귀적으로 적용하여 위상 정렬을 수행합니다. 핵심 원리는 다음과 같습니다. 어떤 정점에서 출발한 DFS가 더 이상 방문할 인접 정점이 없어 종료되는 시점에 해당 정점을 스택에 push하고, 모든 정점의 탐색이 끝난 후 스택에서 pop하며 출력하면 위상 정렬 결과를 얻을 수 있습니다.
시작
함수 topologicalSort():
a) 현재 노드를 방문 처리한다.
b) 이 정점에 인접한 모든 정점에 대해 재귀 호출한다.
c) 현재 정점을 결과를 저장하는 스택에 push한다.
끝
시작
재귀 함수 topologicalSort()를 호출하는 함수 topoSort():
a) 모든 정점을 미방문 상태로 표시한다.
b) topologicalSort() 함수를 호출한다.
c) 결과를 출력한다.
끝C++ 예제 코드
#include<iostream>
#include <list>
#include <stack>
using namespace std;
class G {
int n;
list<int> *adj;
// 함수 선언
void topologicalSort(int v, bool visited[], stack<int> &Stack);
public:
G(int n); // 생성자
void addEd(int v, int w);
void topoSort();
};
G::G(int n) {
this->n = n;
adj = new list<int>[n];
}
// 그래프에 간선 추가
void G::addEd(int v, int w) {
adj[v].push_back(w); // v의 리스트에 w 추가
}
void G::topologicalSort(int v, bool visited[], stack<int> &Stack) {
visited[v] = true; // 현재 노드를 방문 처리
list<int>::iterator i;
// 현재 정점에 인접한 모든 정점에 대해 재귀 호출
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSort(*i, visited, Stack);
// 현재 정점을 결과 스택에 push
Stack.push(v);
}
void G::topoSort() {
stack<int> Stack;
bool *visited = new bool[n];
// 모든 정점을 미방문 상태로 초기화
for (int i = 0; i < n; i++)
visited[i] = false;
// 아직 방문하지 않은 모든 정점에 대해 위상 정렬 수행
for (int i = 0; i < n; i++)
if (visited[i] == false)
topologicalSort(i, visited, Stack);
// 스택의 내용을 pop하며 출력
while (Stack.empty() == false) {
cout << Stack.top() << " ";
Stack.pop();
}
}
int main() {
G g(6);
g.addEd(4, 2);
g.addEd(5, 1);
g.addEd(4, 0);
g.addEd(3, 1);
g.addEd(1, 3);
g.addEd(3, 2);
cout << "Topological Sort of the given graph \n";
g.topoSort();
return 0;
}실행 결과
Topological Sort of the given graph 5 4 1 3 2 0
결과 해석
실행 결과에서 정점 5와 4가 가장 먼저 출력되고, 정점 0이 마지막에 출력되는 것을 확인할 수 있습니다. DFS 기반 위상 정렬은 각 정점의 탐색이 완료되는 시점에 스택에 정점을 저장하므로, 스택에서 꺼내는(pop) 순서가 곧 위상 정렬 순서가 됩니다. 또한 정점의 개수를 V, 간선의 개수를 E라고 할 때, 이 알고리즘의 시간 복잡도는 O(V + E)로 매우 효율적입니다.