유향 비순환 그래프(Directed Acyclic Graph, DAG)에서는 토폴로지 정렬(Topological Sort)을 사용하여 모든 정점을 선형 순서로 나열할 수 있습니다.
다만 토폴로지 정렬은 오직 유향 비순환 그래프에서만 동작한다는 점에 유의해야 합니다. 또한 하나의 DAG에는 서로 다른 여러 개의 올바른 토폴로지 정렬 결과가 존재할 수 있습니다.
이번 글에서는 토폴로지 정렬을 활용하여 그래프 내부에 사이클(cycle)이 존재하는지 판별하는 C++ 프로그램을 자세히 살펴보겠습니다.
예시 개요
그래프의 간선 정보를 인접 행렬 형태로 입력받은 뒤, 깊이 우선 탐색(DFS) 기반의 토폴로지 정렬을 수행하고, 전치 그래프(transposed graph)를 이용해 한 번 더 탐색을 진행하여 사이클 여부를 최종적으로 판단합니다.
알고리즘
Topological Sort:
Begin
topo_sort(int *v, int T_S[][5], int i) 함수 선언
a = new NodeInfo.
a->n = i
a->S_Time = cn.
push_node(a) 함수를 호출하여 데이터 삽입.
v[i] = 1.
for (int j = 0; j < 5; j++)
if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1)) then
continue.
else if (T_S[i][j] == 1 && v[j] == 0) then
cn++.
topo_sort(v, T_S, j) 함수 재귀 호출.
cn++.
a = pop().
a->L_Time = cn.
Store_Node(a).
End.동작 원리
핵심 아이디어는 다음과 같습니다.
1. 먼저 원본 그래프에 대해 DFS 기반 토폴로지 정렬을 수행하여 각 정점의 시작 시간(S_Time)과 종료 시간(L_Time)을 기록합니다.
2. 정렬된 순서대로 노드를 저장한 뒤, 간선의 방향을 뒤집은 전치 그래프를 생성합니다.
3. 전치 그래프에서 다시 탐색을 수행하면서 특정 노드를 찾지 못하면(flag 값 설정) 그래프에 사이클이 없는 것으로 판단하고, 그렇지 않으면 사이클이 존재하는 것으로 출력합니다.
C++ 코드 예제
#include<iostream>
#include<conio.h>
using namespace std;
struct NodeInfo {
int n;
int L_Time, S_Time;
}
*a = NULL;
struct Node {
NodeInfo *ptr;
Node *nxt;
}
*t = NULL, *b = NULL, *npt = NULL;
struct Node_Link {
Node_Link *lk;
NodeInfo *ptr1;
}
*hd = NULL, *m = NULL, *n = NULL, *npt1 = NULL;
int cn = 0;
bool flag = false;
void push_node(NodeInfo *pt) { //데이터 삽입
npt = new Node;
npt->ptr = pt;
npt->nxt = NULL;
if (t == NULL) {
t = npt;
} else {
npt->nxt = t;
t = npt;
}
}
NodeInfo *pop() {
if (t == NULL) {
cout<<"underflow\n";
} else {
b = t;
t = t->nxt;
return(b->ptr);
delete(b);
}
}
void Store_Node(NodeInfo *pt1) { //데이터 저장
npt1 = new Node_Link;
npt1->ptr1 = pt1;
npt1->lk = NULL;
if (cn == 0) {
hd = npt1;
m = hd;
m->lk = NULL;
cn++;
} else {
m = hd;
npt1->lk = m;
hd = npt1;
}
}
void delete_node(int x) { //노드 삭제
m = hd;
if ((m->ptr1)->n == x) {
hd = hd->lk;
delete(m);
} else {
while ((m->ptr1)->n != x && m->lk != NULL) {
n = m;
m = m->lk;
}
if ((m->ptr1)->n == x) {
n->lk = m->lk;
delete(m);
} else if (m->lk == NULL) {
flag = true;
cout<<"There is no circle in this graph\n";
}
}
}
void topo_sort(int *v, int T_S[][5], int i) { //토폴로지 정렬 수행
a = new NodeInfo;
a->n = i;
a->S_Time = cn;
push_node(a);
v[i] = 1;
for (int j = 0; j < 5; j++) {
if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1))
continue;
else if(T_S[i][j] == 1 && v[j] == 0) {
cn++;
topo_sort(v,T_S,j);
}
}
cn++;
a = pop();
a->L_Time = cn;
Store_Node(a);
return;
}
void topologic_sort(int *v, int T_S[][5], int i) {
v[i] = 1;
delete_node(i);
for (int j = 0; j < 5; j++) {
if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1)) {
continue;
} else if(T_S[i][j] == 1 && v[j] == 0) {
topologic_sort(v, T_S, j);
}
}
return;
}
void Insert_Edge(int T_S[][5], int source, int destination) { //간선 값 삽입
T_S[source][destination] = 1;
return;
}
int main() {
int v[5], T_S[5][5], T_S_N[5][5], cn = 0, a, b;
for (int i = 0; i < 5; i++) {
v[i] = 0;
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
T_S[i][j] = 0;
}
}
while (cn < 5) {
cout<<"Enter the source: ";
cin>>a;
cout<<"Enter the destination: ";
cin>>b;
cout<<endl;
Insert_Edge(T_S, a, b);
cn++;
}
topo_sort(v, T_S, 0);
for (int i = 0; i < 5; i++) {
v[i] = 0;
for (int j = 0; j < 5; j++) {
T_S_N[j][i] = T_S[i][j];
}
}
if (hd != NULL) {
topologic_sort(v, T_S_N, (hd->ptr1)->n);
if (flag == false) {
cout<<"There is a cycle in this graph...\n";
}
}
getch();
}실행 결과
아래 예제에서는 0 → 1 → 2 → 3 → 4 → 0으로 이어지는 간선을 입력하여 마지막 정점이 다시 시작 정점으로 돌아오는 구조를 만들었습니다. 실행 결과 사이클이 존재함을 정확히 감지하는 것을 확인할 수 있습니다.
Enter the source: 0 Enter the destination: 1 Enter the source: 1 Enter the destination: 2 Enter the source: 2 Enter the destination: 3 Enter the source: 3 Enter the destination: 4 Enter the source: 4 Enter the destination: 0 There is a cycle in this graph...
마무리
이처럼 토폴로지 정렬과 전치 그래프를 조합하면 별도의 복잡한 알고리즘 없이도 그래프의 사이클 존재 여부를 효과적으로 판별할 수 있습니다. 이 기법은 작업 스케줄링, 의존성 분석 등 DAG 구조를 다루는 다양한 분야에서 유용하게 활용됩니다.