Chương trình C ++ để tìm cạnh phản hồi tốt được đặt trong biểu đồ

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 có 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;
}i
nt 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