グラフで適切なフィードバックエッジセットを見つけるための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