그래프 이론에서 정방향 에지(forward edge)란 깊이 우선 탐색(DFS)을 수행하는 도중, 어떤 노드가 자신의 자손(descendant) 노드를 가리키지만 트리 에지(tree edge)에는 해당하지 않는 간선을 의미합니다. 이번 글에서는 인접 행렬로 표현된 그래프에서 모든 정방향 에지를 찾아내는 C++ 프로그램을 살펴보겠습니다.
이 프로그램은 DFS를 기반으로 동작하며, 탐색 과정에서 각 노드의 시작 시간(S_Time)과 종료 시간(L_Time)을 기록합니다. 이미 방문이 완료된 노드로 향하는 간선을 발견하면, 현재 노드의 시작 시간이 해당 노드의 시작 시간보다 앞서는지 비교하여 정방향 에지 여부를 판별합니다.
알고리즘
topo() 함수 의사코드
시작
topo() 함수 선언
정수형 포인터 v, m[][5], i를 선언한다.
x = new Node_Inf
x->n = i
x->S_Time = c
Push_Node(x) 함수를 호출한다.
v[i] = 1
for (int j = 0; j < 5; j++)
if (m[i][j] == 0)이면
continue;
else if (m[i][j] == 1 && v[j] == 1 && !Exist_in_Stack(j))이면
if (x->S_Time < srch_Node(j))이면
"Forward Edge is between"을 출력한다.
정방향 에지의 값을 출력한다.
continue;
else if (m[i][j] == 1 && v[j] == 0)이면
c++;
"Forward Edge is between"을 출력한다.
정방향 에지의 값을 출력한다.
topo(v, m, j) 함수를 호출한다.
c++;
x = pop()
x->L_Time = c
노드에 값을 저장하기 위해 Store_Node(x) 함수를 호출한다.
반환한다.
끝.
C++ 전체 소스 코드
#include<iostream>
#include<conio.h>
using namespace std;
struct Node_Inf {
int n;
int L_Time, S_Time;
}
*x = NULL, *y = NULL;
struct Node_1 {
Node_Inf *ptn;
Node_1 *nxt;
}
*tp = NULL, *p = NULL, *npr = NULL;
struct Node_2 {
Node_2 *lnk;
Node_Inf *ptn1;
}
*hd = NULL, *m = NULL, *n = NULL, *npr1 = NULL;
int c = 0;
void Push_Node(Node_Inf *ptr) {
npr = new Node_1;
npr->ptn = ptr;
npr->nxt = NULL;
if (tp == NULL) {
tp = npr;
} else {
npr->nxt = tp;
tp = npr;
}
}
Node_Inf *pop() {
if (tp == NULL) {
cout<<"underflow\n";
} else {
p = tp;
tp = tp->nxt;
return(p->ptn);
delete(p);
}
}
void Store_Node(Node_Inf *ptr1) {
npr1 = new Node_2;
npr1->ptn1 = ptr1;
npr1->lnk = NULL;
if (c == 0) {
hd = npr1;
m = hd;
m->lnk = NULL;
c++;
} else {
m = hd;
npr1->lnk = m;
hd = npr1;
}
}
int srch_Node(int j) {
Node_2 *t = hd;
while (t != NULL) {
if ((t->ptn1)->n == j)
{
break;
} else {
t = t->lnk;
continue;
}
}
return (t->ptn1)->L_Time;
}
int Exist_in_Stack(int j) {
int flag = 0;
p = tp;
while (p != NULL) {
if ((p->ptn)->n == j) {
flag = 1;
return flag;
}
p = p->nxt;
}
return flag;
}
void topo(int *v, int m[][5], int i) {
x = new Node_Inf;
x->n = i;
x->S_Time = c;
Push_Node(x);
v[i] = 1;
for (int j = 0; j < 5; j++) {
if (m[i][j] == 0)
continue;
else if (m[i][j] == 1 && v[j] == 1 && !Exist_in_Stack(j)) {
if (x->S_Time < srch_Node(j)) {
cout<<"\nForward Edge is between "<<i<<" and "<<j<<endl;
}
continue;
} else if (m[i][j] == 1 && v[j] == 0) {
c++;
cout<<"\nForward Edge is between "<<i<<" and "<<j<<endl;
topo(v,m,j);
}
}
c++;
x = pop();
x->L_Time = c;
Store_Node(x);
return;
}
int main() {
int v[5],m[5][5];
for (int i = 0; i < 5; i++)
v[i] = 0;
for (int i = 0; i < 5; i++) {
cout<<" Enter the values of matrix::"<<i + 1<<endl;
for(int j = 0; j < 5; j++) {
cin>>m[i][j];
}
}
topo(v,m,0);
getch();
}코드 주요 구성 요소
- Node_Inf 구조체: 노드 번호(n)와 시작 시간(S_Time), 종료 시간(L_Time)을 함께 저장합니다.
- Push_Node() / pop(): DFS 탐색 경로를 추적하기 위한 스택 삽입·삭제 연산을 담당합니다.
- Store_Node(): 탐색이 완료된 노드를 연결 리스트 형태로 저장합니다.
- srch_Node(): 저장된 노드 목록에서 특정 노드의 종료 시간을 조회합니다.
- Exist_in_Stack(): 특정 노드가 현재 스택에 존재하는지 확인하여, 정방향 에지와 다른 유형의 간선을 구분하는 데 활용됩니다.
실행 결과
Enter the values of matrix:1 0 1 0 1 0 Enter the values of matrix:2 1 0 0 1 0 Enter the values of matrix:3 1 0 0 0 1 Enter the values of matrix:4 0 1 1 0 0 Enter the values of matrix:5 1 1 0 0 0 Forward Edge is between 0 and 1 Forward Edge is between 1 and 3 Forward Edge is between 3 and 2 Forward Edge is between 2 and 4 Forward Edge is between 0 and 3
위 실행 결과에서 프로그램은 먼저 5×5 크기의 인접 행렬을 입력받습니다. 이후 노드 0에서 DFS 탐색을 시작하고, 탐색 과정에서 감지된 정방향 에지들을 순서대로 출력합니다. 예를 들어 "Forward Edge is between 0 and 3"이라는 결과는 노드 0에서 노드 3으로 향하는 간선이 정방향 에지임을 의미합니다.