บทนำ
ในโปรแกรมนี้เราจะหา Feedback Arc Set ซึ่งเป็นชุดของเส้นเชื่อมที่เมื่อลบออกจากกราฟ จะทำให้กราฟกลายเป็น Directed Acyclic Graph (DAG)
อัลกอริทึม
Begin
function 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
while 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
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
ถ้า 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
End
ตัวอย่างโค้ด 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;
}
}
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
