C++ Program to Check if Graph is DAG

«
»
This is a C++ Program to check whether graph is DAG. In mathematics and computer science, a directed acyclic graph (DAG Listeni/’dæg/), is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again.

Here is source code of the C++ Program to Check Whether Graph is DAG. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<conio.h>
  4. using namespace std;
  5. int c = 0;
  6. struct adj_list
  7. {
  8.         int dest;
  9.         adj_list *next;
  10. }*np = NULL, *np1 = NULL, *p = NULL, *q = NULL;
  11. struct Graph
  12. {
  13.         int v;
  14.         adj_list *ptr;
  15. } array[6];
  16. void addReverseEdge(int src, int dest)
  17. {
  18.     np1 = new adj_list;
  19.     np1->dest = src;
  20.     np1->next = NULL;
  21.     if (array[dest].ptr == NULL)
  22.     {
  23.         array[dest].ptr = np1;
  24.         q = array[dest].ptr;
  25.         q->next = NULL;
  26.     }
  27.     else
  28.     {
  29.         q = array[dest].ptr;
  30.         while (q->next != NULL)
  31.         {
  32.             q = q->next;
  33.         }
  34.         q->next = np1;
  35.     }
  36. }
  37. void addEdge(int src, int dest)
  38. {
  39.     np = new adj_list;
  40.     np->dest = dest;
  41.     np->next = NULL;
  42.     if (array[src].ptr == NULL)
  43.     {
  44.         array[src].ptr = np;
  45.         p = array[src].ptr;
  46.         p->next = NULL;
  47.     }
  48.     else
  49.     {
  50.         p = array[src].ptr;
  51.         while (p->next != NULL)
  52.         {
  53.             p = p->next;
  54.         }
  55.         p->next = np;
  56.     }
  57.     //addReverseEdge(src, dest);
  58. }
  59. void print_graph(int n)
  60. {
  61.     for (int i = 0; i < n; i++)
  62.     {
  63.         cout << "Adjacency List of " << array[i].v << ": ";
  64.         while (array[i].ptr != NULL)
  65.         {
  66.             cout << (array[i].ptr)->dest << " ";
  67.             array[i].ptr = (array[i].ptr)->next;
  68.         }
  69.         cout << endl;
  70.     }
  71. }
  72.  
  73. int checkDAG(int n)
  74. {
  75.     int count = 0;
  76.     int size = n - 1;
  77.     for (int i = 0; i < n; i++)
  78.     {
  79.         //cout << "Adjacency List of " << array[i].v << ": ";
  80.         if (count == size)
  81.         {
  82.             return 1;
  83.         }
  84.         if (array[i].ptr == NULL)
  85.         {
  86.             count++;
  87.             for (int j = 0; j < n; j++)
  88.             {
  89.  
  90.                 while (array[j].ptr != NULL)
  91.                 {
  92.                     if ((array[j].ptr)->dest == (array[i].ptr)->dest)
  93.                     {
  94.                         (array[j].ptr)->dest = -1;
  95.                     }
  96.                     array[i].ptr = (array[i].ptr)->next;
  97.                 }
  98.             }
  99.  
  100.         }
  101.     }
  102.     return 0;
  103. }
  104. int main()
  105. {
  106.     int n = 6;
  107.     cout << "Number of vertices: " << n << endl;
  108.  
  109.     for (int i = 0; i < n; i++)
  110.     {
  111.         array[i].v = i;
  112.         array[i].ptr = NULL;
  113.     }
  114.     addEdge(0, 1);
  115.     addEdge(1, 2);
  116.     addEdge(1, 3);
  117.     addEdge(3, 4);
  118.     addEdge(4, 5);
  119.     addEdge(5, 3);
  120.     addEdge(5, 2);
  121.     print_graph(n);
  122.     cout << "The given graph is 'Directed Acyclic Graph' :";
  123.     if (checkDAG(n) == 1)
  124.         cout << " True";
  125.     else
  126.         cout << " False";
  127. }

Output:

advertisement
$ g++ CheckDAG.cpp
$ a.out
 
Number of vertices: 6
Adjacency List of 0: 1 
Adjacency List of 1: 2 3 
Adjacency List of 2: 
Adjacency List of 3: 4 
Adjacency List of 4: 5 
Adjacency List of 5: 3 2 
The given graph is 'Directed Acyclic Graph' : True
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.