Chương trình C ++ để kiểm tra xem đồ thị có phải là DAG hay không

Đồ thị xoay chiều có hướng (DAG) là đồ thị có hướng và không có chu trình nối các cạnh khác. Các cạnh của đồ thị này đi theo một hướng. Đây là một chương trình C ++ để kiểm tra xem biểu đồ có phải là DAG hay không.

Thuật toán

Begin
Function checkDAG(int n):
   intialize count = 0
   intialize size = n - 1
   for i = 0 to n-1
      if (count == size)
         return 1
      done
      if (arr[i].ptr == NULL)
         increment count
         for j = 0 to n-1
            while (arr[j].ptr != NULL)
               if ((arr[j].ptr)->d == (arr[i].ptr)->d)
                  (arr[j].ptr)->d = -1
               done
            arr[i].ptr = (arr[i].ptr)->next
            done
         done
      done
   done
   return 0
End

Mã mẫu

#include<iostream>
using namespace std;
int c = 0;
struct ad_list { //A structure of type adj_list
   int d;
   ad_list *next;
}
*np = NULL, *np1 = NULL, *p = NULL, *q = NULL;
struct Gr { //A structure of type Gr
   int v;
   ad_list *ptr;
}
arr[6];
void addRevEdge(int s, int d) { //add reverse edges in the graph
   np1 = new ad_list;
   np1->d = s;
   np1->next = NULL;
   if (arr[d].ptr == NULL) {
      arr[d].ptr = np1;
      q = arr[d].ptr;
      q->next = NULL;
   } else {
      q = arr[d].ptr;
      while (q->next != NULL) {
         q = q->next;
      }
      q->next = np1;
   }
}
void addEdge(int s, int d) { // add edges in the graph
   np = new ad_list;
   np->d = d;
   np->next = NULL;
   if (arr[s].ptr == NULL) {
      arr[s].ptr = np;
      p = arr[s].ptr;
      p->next = NULL;
   } else {
      p = arr[s].ptr;
      while (p->next != NULL) {
         p = p->next;
      }
      p->next = np;
   }
}
void print_g(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)->d<< " ";
         arr[i].ptr = (arr[i].ptr)->next;
      }
      cout << endl;
   }
}
int checkDAG(int n) {
   int count = 0;
   int size = n - 1;
   for (int i = 0; i < n; i++) {
      if (count == size) {
         return 1;
      }
      if (arr[i].ptr == NULL) {
         count++;
         for (int j = 0; j < n; j++) {
            while (arr[j].ptr != NULL) {
               if ((arr[j].ptr)->d == (arr[i].ptr)->d) {
                  (arr[j].ptr)->d = -1;
               }
               arr[i].ptr = (arr[i].ptr)->next;
            }
         }
      }
   }
   return 0;
}
int main() {
   int v = 4;
   cout << "Number of vertices: " << v << endl;
   for (int i = 0; i < v; i++) {
      arr[i].v = i;
      arr[i].ptr = NULL;
   }
   addEdge(1, 0);
   addEdge(3, 1);
   addEdge(2, 1);
   addEdge(0, 3);
   addEdge(4, 1);
   print_g(v);
   cout << "The given graph is 'Directed Acyclic Graph' :";
   if (checkDAG(v) == 1)
      cout << " yes";
   else
      cout << " no";
}

Đầu ra

Number of vertices: 4
Adjacency List of 0: 3
Adjacency List of 1: 0
Adjacency List of 2: 1
Adjacency List of 3: 1
The given graph is 'Directed Acyclic Graph' : yes