Trong Chương trình này, về cơ bản, chúng ta sẽ tìm thấy một tập hợp cung phản hồi chứa các cạnh mà khi loại bỏ khỏi biểu đồ, biểu đồ sẽ trở thành biểu đồ xoay chiều có hướng.
Thuật toán
Begin function checkCG(int n) : n: number of vertices. arr: struct graph variable. Initialize cnt = 0 and size = (n-1). For i = 0 to n-1 if (cnt == size) return 0 if (arr[i].ptr == NULL) Increase cnt. for j = 0 to 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 Done Done Done Done initialize visited[n + 1] For i = 0 to n-1 while (arr[i].ptr != NULL) Print (arr[i].ptr)->des visited[i] = 1 for j = 0 to n-1 while (arr[j].ptr != NULL) print (arr[j].ptr)->des if (visited[arr[j].v] == 1) print arr[i].v << " - " << arr[j].v Done arr[j].ptr = (arr[j].ptr)->next Done Done arr[i].ptr = (arr[i].ptr)->next Done Done return 1 End
Ví dụ
#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) //to add reverse edge in the graph {
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) // to add edge in the graph {
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) //to print graph {
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;
}
}
//to check whether the graph is directed acyclic graph or not.
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";
} Đầu ra
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