이 글에서는 그래프 이론의 중요한 개념 중 하나인 피드백 아크 집합(Feedback Arc Set)을 찾는 C++ 프로그램을 다룹니다. 피드백 아크 집합이란, 그래프에서 특정 간선들을 제거했을 때 그래프가 방향 비순환 그래프(DAG, Directed Acyclic Graph), 즉 순환이 없는 방향 그래프가 되도록 만들어 주는 간선들의 집합을 의미합니다.
알고리즘
시작
함수 checkCG(int n):
n: 정점의 개수
arr: 그래프 구조체 변수
cnt = 0, size = (n-1)로 초기화
i = 0부터 n-1까지 반복
만약 (cnt == size)이면
0을 반환
만약 (arr[i].ptr == NULL)이면
cnt 증가
j = 0부터 n-1까지 반복
arr[j].ptr이 NULL이 아닐 동안
만약 ((arr[j].ptr)->des == (arr[i].ptr)->des)이면
(arr[j].ptr)->des = -1 대입
arr[i].ptr = (arr[i].ptr)->next
반복 끝
반복 끝
조건문 끝
반복 끝
visited[n + 1] 배열 초기화
i = 0부터 n-1까지 반복
arr[i].ptr이 NULL이 아닐 동안
(arr[i].ptr)->des 출력
visited[i] = 1 대입
j = 0부터 n-1까지 반복
arr[j].ptr이 NULL이 아닐 동안
(arr[j].ptr)->des 출력
만약 (visited[arr[j].v] == 1)이면
arr[i].v << " - " << arr[j].v 출력
반복 끝
arr[j].ptr = (arr[j].ptr)->next
반복 끝
반복 끝
arr[i].ptr = (arr[i].ptr)->next
반복 끝
반복 끝
1을 반환
끝예제 코드
#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 (array[des].ptr == NULL) {
array[des].ptr = np1;
q = array[des].ptr;
q->next = NULL;
} else {
q = array[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 (array[sr].ptr == NULL) {
array[sr].ptr = np;
p = array[sr].ptr;
p->next = NULL;
} else {
p = array[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 " << array[i].v << ": ";
while (array[i].ptr != NULL) {
cout << (array[i].ptr)->des << " ";
array[i].ptr = (array[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 (array[i].ptr == NULL) {
cnt++;
for (int j = 0; j < n; j++) {
while (array[j].ptr != NULL) {
if ((array[j].ptr)->des == (array[i].ptr)->des) {
(array[j].ptr)->des = -1;
}
array[i].ptr = (array[i].ptr)->next;
}
}
}
}
cout << "after checking dag";
int visited[n + 1];
for (int i = 0; i < n; i++) {
while (array[i].ptr != NULL) {
cout << (array[i].ptr)->des << " ";
visited[i] = 1;
for (int j = 0; j < n; j++) {
while (array[j].ptr != NULL) {
cout << (array[j].ptr)->des << " ";
if (visited[array[j].v] == 1) {
cout << array[i].v << " - " << array[j].v;
}
array[j].ptr = (array[j].ptr)->next;
}
cout << endl;
}
array[i].ptr = (array[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++) {
array[i].v = i;
array[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
실행 결과를 보면 먼저 정점의 개수와 각 정점의 인접 리스트가 출력됩니다. 이후 checkCG 함수가 그래프에 순환이 존재하는지 검사하고, 순환을 깨기 위해 제거해야 할 간선들을 피드백 아크 집합으로 찾아냅니다. 위 예제에서는 별도로 제거할 간선이 없어 "None"이 출력되었습니다. 만약 그래프에 순환이 존재한다면, 해당 순환을 끊는 데 필요한 간선들이 피드백 아크 집합으로 출력됩니다.