Advertisement
Guest User

Untitled

a guest
Mar 19th, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. // A C++ Program to detect cycle in a graph
  2. #include<iostream>
  3. #include <list>
  4. #include <limits.h>
  5.  
  6. using namespace std;
  7.  
  8. class Graph
  9. {
  10.     int V; // No. of vertices
  11.     list<int> *adj; // Pointer to an array containing adjacency lists
  12.     bool isCyclicUtil(int v, bool visited[]); // used by isCyclic()
  13. public:
  14.     Graph(int V); // Constructor
  15.     void addEdge(int v, int w); // to add an edge to graph
  16.     bool isCyclic(); // returns true if there is a cycle in this graph
  17. };
  18.  
  19. Graph::Graph(int V)
  20. {
  21.     this->V = V;
  22.     adj = new list<int>[V];
  23. }
  24.  
  25. void Graph::addEdge(int v, int w)
  26. {
  27.     adj[v].push_back(w); // Add w to v’s list.
  28. }
  29.  
  30. // This function is a variation of DFSUytil() in https://www.geeksforgeeks.org/archives/18212
  31. bool Graph::isCyclicUtil(int v, bool visited[])
  32. {
  33.     if(visited[v] == false)
  34.     {
  35.         // Mark the current node as visited and part of recursion stack
  36.         visited[v] = true;
  37.  
  38.         // Recur for all the vertices adjacent to this vertex
  39.         list<int>::iterator i;
  40.         for(i = adj[v].begin(); i != adj[v].end(); ++i)
  41.         {
  42.             if (visited[*i])
  43.                 return true;
  44.             else
  45.                isCyclicUtil(*i, visited);
  46.         }
  47.  
  48.     }
  49.     return false;
  50. }
  51.  
  52. // Returns true if the graph contains a cycle, else false.
  53. // This function is a variation of DFS() in https://www.geeksforgeeks.org/archives/18212
  54. bool Graph::isCyclic()
  55. {
  56.     // Mark all the vertices as not visited and not part of recursion
  57.     // stack
  58.     bool *visited = new bool[V];
  59.     for(int i = 0; i < V; i++)
  60.     {
  61.         visited[i] = false;
  62.     }
  63.  
  64.     // Call the recursive helper function to detect cycle in different
  65.     // DFS trees
  66.     for(int i = 0; i < V; i++)
  67.         if (isCyclicUtil(i, visited))
  68.             return true;
  69.  
  70.     return false;
  71. }
  72.  
  73. int main()
  74. {
  75.     // Create a graph given in the above diagram
  76.     Graph g(4);
  77.     g.addEdge(0, 1);
  78.     g.addEdge(0, 2);
  79.     g.addEdge(1, 2);
  80.     g.addEdge(2, 0);
  81.     g.addEdge(2, 3);
  82.     g.addEdge(3, 3);
  83.  
  84.     if(g.isCyclic())
  85.         cout << "Graph contains cycle";
  86.     else
  87.         cout << "Graph doesn't contain cycle";
  88.     return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement