C++ Program to Check Cycle in a Graph using Graph Traversal

«
»
This C++ Program checks Cycle in a Graph using Graph traversal.

Here is source code of the C++ Program to check Cycle in a Graph using Graph traversal. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Check Cycle in a Graph using Graph Traversal
  3.  */
  4. #include <iostream>
  5. #include <list>
  6. #include <climits>
  7. #include <cstdlib>
  8. using namespace std;
  9. /**
  10.  * Class Declaration
  11.  */
  12. class Graph
  13. {
  14.     private:
  15.         int V;
  16.         list<int> *adj;
  17.         bool isCyclicUtil(int v, bool visited[], bool *rs);
  18.     public:
  19.         Graph(int V);
  20.         void addEdge(int v, int w);
  21.         bool isCyclic();
  22. };
  23. /**
  24.  * Constructor
  25.  */
  26. Graph::Graph(int V)
  27. {
  28.     this->V = V;
  29.     adj = new list<int>[V];
  30. }
  31. /**
  32.  * Add edge from v to w
  33.  */
  34. void Graph::addEdge(int v, int w)
  35. {
  36.     adj[v].push_back(w);
  37. }
  38. /**
  39.  * isCyclic Utility function
  40.  */
  41. bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
  42. {
  43.     if (visited[v] == false)
  44.     {
  45.         visited[v] = true;
  46.         recStack[v] = true;
  47.         list<int>::iterator i;
  48.         for(i = adj[v].begin(); i != adj[v].end(); ++i)
  49.         {
  50.             if (!visited[*i] && isCyclicUtil(*i, visited, recStack))
  51.                 return true;
  52.             else if (recStack[*i])
  53.                 return true;
  54.         }
  55.     }
  56.     recStack[v] = false;
  57.     return false;
  58. }
  59. /**
  60.  * Check if Graph is Cyclic
  61.  */
  62. bool Graph::isCyclic()
  63. {
  64.     bool visited[V], recStack[V];
  65.     for (int i = 0; i < V; i++)
  66.     {
  67.         visited[i] = false;
  68.         recStack[i] = false;
  69.     }
  70.     for (int i = 0; i < V; i++)
  71.         if (isCyclicUtil(i, visited, recStack))
  72.             return true;
  73.     return false;
  74. }
  75. /**
  76.  * Main Contains Menu
  77.  */
  78. int main()
  79. {
  80.     int nodes, fedge, tedge, ch;
  81.     cout<<"Enter number of nodes: ";
  82.     cin>>nodes;
  83.     Graph g(nodes);
  84.     while (1)
  85.     {
  86.         cout<<"---------------------------------"<<endl;
  87.         cout<<"Check Cycle Using Graph Traversal"<<endl;
  88.         cout<<"---------------------------------"<<endl;
  89.         cout<<"1.Add edges to connect the graph"<<endl;
  90.         cout<<"2.Check if cycle exists"<<endl;
  91.         cout<<"3.Exit"<<endl;
  92.         cout<<"Enter your Choice: ";
  93.         cin>>ch;
  94.         switch (ch)
  95.         {
  96.         case 1:
  97.             cout<<"Enter node of from egde(0 - "<<nodes - 1<<"): ";
  98.             cin>>fedge;
  99.             cout<<"Enter node of to egde(0 - "<<nodes - 1<<"): ";
  100.             cin>>tedge;
  101.             g.addEdge(fedge, tedge);
  102.             break;
  103.         case 2:
  104.             if (g.isCyclic())
  105.                 cout << "Graph contains cycle"<<endl;
  106.             else
  107.                 cout << "Graph doesn't contain cycle"<<endl;
  108.             break;
  109.         case 3:
  110.             exit(1);
  111.         default:
  112.             cout<<"Wrong Choice"<<endl;
  113.         }
  114.     }
  115.     return 0;
  116. }

advertisement
$ g++ check_cycle.cpp
$ a.out
Enter number of nodes: 5
---------------------------------
Check Cycle Using Graph Traversal
---------------------------------
1.Add edges to connect the graph
2.Check if cycle exists
3.Exit
Enter your Choice: 1
Enter node of from egde(0 - 4): 0  
Enter node of to egde(0 - 4): 1
---------------------------------
Check Cycle Using Graph Traversal
---------------------------------
1.Add edges to connect the graph
2.Check if cycle exists
3.Exit
Enter your Choice: 1
Enter node of from egde(0 - 4): 0 
Enter node of to egde(0 - 4): 2
---------------------------------
Check Cycle Using Graph Traversal
---------------------------------
1.Add edges to connect the graph
2.Check if cycle exists
3.Exit
Enter your Choice: 1
Enter node of from egde(0 - 4): 1
Enter node of to egde(0 - 4): 2
---------------------------------
Check Cycle Using Graph Traversal
---------------------------------
1.Add edges to connect the graph
2.Check if cycle exists
3.Exit
Enter your Choice: 1
Enter node of from egde(0 - 4): 3
Enter node of to egde(0 - 4): 1
---------------------------------
Check Cycle Using Graph Traversal
---------------------------------
1.Add edges to connect the graph
2.Check if cycle exists
3.Exit
Enter your Choice: 1
Enter node of from egde(0 - 4): 4
Enter node of to egde(0 - 4): 3
---------------------------------
Check Cycle Using Graph Traversal
---------------------------------
1.Add edges to connect the graph
2.Check if cycle exists
3.Exit
Enter your Choice: 1
Enter node of from egde(0 - 4): 2
Enter node of to egde(0 - 4): 0
---------------------------------
Check Cycle Using Graph Traversal
---------------------------------
1.Add edges to connect the graph
2.Check if cycle exists
3.Exit
Enter your Choice: 2
Graph contains cycle
---------------------------------
Check Cycle Using Graph Traversal
---------------------------------
1.Add edges to connect the graph
2.Check if cycle exists
3.Exit
Enter your Choice: 3
 
 
------------------
(program exited with code: 1)
Press return to continue

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

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

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.