이 글에서는 피드백 아크 집합(Feedback Arc Set)을 찾는 C++ 프로그램을 살펴봅니다. 피드백 아크 집합에 속한 간선들을 그래프에서 제거하면, 해당 그래프는 사이클이 없는 방향성 비순환 그래프(DAG, Directed Acyclic Graph)로 변환됩니다. 이는 위상 정렬 등 선형 확장(Linear Extension)을 구하기 위한 필수 과정입니다.
핵심 개념
방향 그래프에 사이클이 존재하면 위상 정렬을 수행할 수 없습니다. 따라서 최소한의 간선을 제거하여 사이클을 끊어야 하는데, 이때 제거 대상이 되는 간선들의 집합을 피드백 아크 집합이라고 합니다. 만약 그래프가 이미 DAG라면 피드백 아크 집합은 존재하지 않습니다.
알고리즘
시작
함수 checkCG(int n):
n: 정점의 개수
arr: graph 구조체 변수
cnt = 0, size = (n-1)로 초기화
i = 0부터 n-1까지 반복
if (cnt == size)
return 0
if (arr[i].ptr == NULL)
cnt 증가
j = 0부터 n-1까지 반복
while (arr[j].ptr != NULL)
if ((arr[j].ptr)->des == (arr[i].ptr)->des)
(arr[j].ptr)->des = -1
arr[i].ptr = (arr[i].ptr)->next
while 종료
for 종료
if 종료
for 종료
visited[n + 1] 배열 초기화
i = 0부터 n-1까지 반복
while (arr[i].ptr != NULL)
(arr[i].ptr)->des 출력
visited[i] = 1
j = 0부터 n-1까지 반복
while (arr[j].ptr != NULL)
(arr[j].ptr)->des 출력
if (visited[arr[j].v] == 1)
arr[i].v와 arr[j].v 연결 정보 출력
while 종료
arr[j].ptr = (arr[j].ptr)->next
for 종료
arr[i].ptr = (arr[i].ptr)->next
while 종료
for 종료
return 1
끝C++ 예제 코드
#include<iostream>
using namespace std;
int c = 0;
struct ad_list {
int des;
ad_list *next;
}*np = NULL, *np1 = NULL, *p = NULL, *q = NULL;
struct Graph {
int v;
ad_list *ptr;
} array[6];
void addRevEdge(int sr, int des) //그래프에 역방향 간선을 추가하는 함수 {
np1 = new ad_list;
np1->des = sr;
np1->next = NULL;
if (arr[des].ptr == NULL) {
arr[des].ptr = np1;
q = arr[des].ptr;
q->next = NULL;
} else {
q = arr[des].ptr;
while (q->next != NULL) {
q = q->next;
}
q->next = np1;
}
}
void addEd(int sr, int des) //그래프에 간선을 추가하는 함수 {
np = new ad_list;
np->des = des;
np->next = NULL;
if (arr[sr].ptr == NULL) {
arr[sr].ptr = np;
p = arr[sr].ptr;
p->next = NULL;
} else {
p = arr[sr].ptr;
while (p->next != NULL) {
p = p->next;
}
p->next = np;
}
}
void print_graph(int n) //그래프를 출력하는 함수 {
for (int i = 0; i < n; i++) {
cout << "Adjacency List of " << arr[i].v << ": ";
while (arr[i].ptr != NULL) {
cout << (arr[i].ptr)->des << " ";
arr[i].ptr = (arr[i].ptr)->next;
}
cout << endl;
}
}
//그래프가 방향성 비순환 그래프(DAG)인지 검사하는 함수.
int checkCG(int n) {
int cnt = 0;
int size = n - 1;
for (int i = 0; i < n; i++) {
if (cnt == size) {
return 0;
}
if (arr[i].ptr == NULL) {
cnt++;
for (int j = 0; j < n; j++) {
while (arr[j].ptr != NULL) {
if ((arr[j].ptr)->des == (arr[i].ptr)->des) {
(arr[j].ptr)->des = -1;
}
arr[i].ptr = (arr[i].ptr)->next;
}
}
}
}
cout<<"after checking dag";
int visited[n + 1];
for (int i = 0; i < n; i++) {
while (arr[i].ptr != NULL) {
cout << (arr[i].ptr)->des << " ";
visited[i] = 1;
for (int j = 0; j < n; j++) {
while (arr[j].ptr != NULL) {
cout << (arr[j].ptr)->des << " ";
if (visited[arr[j].v] == 1) {
cout << arr[i].v << " - " << arr[j].v;
}
arr[j].ptr = (arr[j].ptr)->next;
}
cout << endl;
}
arr[i].ptr = (arr[i].ptr)->next;
}
cout << endl;
}
return 1;
}
int main() {
int n = 5;
cout << "Number of vertices: " << n << endl;
for (int i = 0; i < n; i++) {
arr[i].v = i;
arr[i].ptr = NULL;
}
addEd(1, 2);
addEd(2, 1);
addEd(0, 1);
addEd(2, 3);
addEd(2, 0);
addEd(5, 4);
addEd(4, 2);
print_graph(n);
cout << "Feedback arc Set: ";
if (checkCG(n) == 0)
cout << " None";
}실행 결과
Number of vertices: 5 Adjacency List of 0: 1 Adjacency List of 1: 2 Adjacency List of 2: 1 3 0 Adjacency List of 3: Adjacency List of 4: 2 Feedback arc Set: None
결과 해석
위 예제에서 그래프는 5개의 정점으로 구성되어 있으며, 각 정점의 인접 리스트가 먼저 출력됩니다. 이후 checkCG 함수가 그래프가 이미 방향성 비순환 그래프인지 검사한 결과, 제거할 간선이 없으므로 피드백 아크 집합이 존재하지 않는다는 의미의 "None"이 출력됩니다. 만약 그래프에 사이클이 존재한다면, 함수는 사이클을 형성하는 간선들을 식별하여 피드백 아크 집합으로 반환하게 됩니다.