그래프에서 좋은 피드백 에지 세트를 찾는 C++ 프로그램

이 프로그램에서 우리는 기본적으로 그래프에서 제거될 때 그래프가 방향성 비순환 그래프가 되는 모서리를 포함하는 피드백 호 세트를 찾을 것입니다.

알고리즘

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

예시

#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";
}

출력

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