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.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

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!
advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn