{"id":25931,"date":"2017-10-25T21:48:42","date_gmt":"2017-10-25T16:18:42","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25931"},"modified":"2017-10-25T21:48:42","modified_gmt":"2017-10-25T16:18:42","slug":"detect-cycle-directed-graph-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/detect-cycle-directed-graph-2\/","title":{"rendered":"Detect Cycle in a Directed Graph"},"content":{"rendered":"

Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false.<\/span> For example, the following graph contains three cycles 0->2->0, 0->1->2->0 and 3->3, so your function must return true<\/p>\n

Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge<\/a> present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS. In the following graph, there are 3 back edges, marked with cross sign. We can observe that these 3 back edges indicate 3 cycles present in the graph.<\/p>\n

For a disconnected graph, we get the DFS forrest as output<\/p>\n[ad type=”banner”]. To detect cycle, we can check for cycle in individual trees by checking back edges.<\/p>\n

To detect a back edge, we can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree. The edge that connects current vertex to the vertex in the recursion stack is back edge. We have used recStack[] array to keep track of vertices in the recursion stack.<\/p>\n

<\/div> 
\/\/ A C++ Program to detect cycle in a graph#include<iostream>#include <list>#include <limits.h> using namespace std; class Graph{    int V;    \/\/ No. of vertices    list<int> *adj;    \/\/ Pointer to an array containing adjacency lists    bool isCyclicUtil(int v, bool visited[], bool *rs);  \/\/ used by isCyclic()public:    Graph(int V);   \/\/ Constructor    void addEdge(int v, int w);   \/\/ to add an edge to graph    bool isCyclic();    \/\/ returns true if there is a cycle in this graph}; Graph::Graph(int V){    this->V = V;    adj = new list<int>[V];} void Graph::addEdge(int v, int w){    adj[v].push_back(w); \/\/ Add w to v\u2019s list.} \/\/ This function is a variation of DFSUytil() in http:\/\/www.geeksforgeeks.org\/archives\/18212bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack){    if(visited[v] == false)    {        \/\/ Mark the current node as visited and part of recursion stack        visited[v] = true;        recStack[v] = true;         \/\/ Recur for all the vertices adjacent to this vertex        list<int>::iterator i;        for(i = adj[v].begin(); i != adj[v].end(); ++i)        {            if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )                return true;            else if (recStack[*i])                return true;        }     }    recStack[v] = false;  \/\/ remove the vertex from recursion stack    return false;} \/\/ Returns true if the graph contains a cycle, else false.\/\/ This function is a variation of DFS() in http:\/\/www.geeksforgeeks.org\/archives\/18212bool Graph::isCyclic(){    \/\/ Mark all the vertices as not visited and not part of recursion    \/\/ stack    bool *visited = new bool[V];    bool *recStack = new bool[V];    for(int i = 0; i < V; i++)    {        visited[i] = false;        recStack[i] = false;    }     \/\/ Call the recursive helper function to detect cycle in different    \/\/ DFS trees    for(int i = 0; i < V; i++)        if (isCyclicUtil(i, visited, recStack))            return true;     return false;} int main(){    \/\/ Create a graph given in the above diagram    Graph g(4);    g.addEdge(0, 1);    g.addEdge(0, 2);    g.addEdge(1, 2);    g.addEdge(2, 0);    g.addEdge(2, 3);    g.addEdge(3, 3);     if(g.isCyclic())        cout << "Graph contains cycle";    else        cout << "Graph doesn't contain cycle";    return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Graph contains cycle<\/pre>\n
Time Complexity of this method is same as time complexity of DFS traversal<\/a> which is O(V+E).<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Detect Cycle in a Directed Graph – Graph Algorithms – Given a directed graph, check whether the graph contains a cycle or not.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,74168,73906],"tags":[76188,76186,76185,76184,76189,76183,76187,76190],"class_list":["post-25931","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-dfs-and-bfs","category-graph-algorithms","tag-detect-cycle-in-a-graph-c-code","tag-detect-cycle-in-directed-graph-c","tag-detect-cycle-in-directed-graph-in-c","tag-detect-cycle-in-directed-graph-java","tag-detect-cycle-in-graph-using-bfs","tag-detect-cycle-in-undirected-graph","tag-detect-cycle-in-undirected-graph-in-c","tag-find-all-cycles-in-a-directed-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25931","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25931"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25931\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25931"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25931"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25931"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}