I want help please don't down-vote.
I want to print the cycle in an undirected graph. I know how to detect cycle in an undirected graph but can't determine how to find the vertices involved in the cycle. Here is the code to find cycle.
code
Can someone please tell me how to modify this so that I can get the vertices in the cycle as well.
I have seen geeksforgeeks article on printing all cycles but I can't understand it. Is there some simpler approach ?
Hello! To do that you can use stack. In DFS you can push visited vertex to stack, and if there is a cycle then all elements from the top of stack (until you reach the last vertex) belong to the cycle
When you do dfs, you can consider vertices of 3 types; unvisited, visited but in the stack, or visited and finished (we called dfs on all their neighbors and returned already).
If your dfs detects a cycle, then all the cycle vertices are the type that's in the stack (they must have been visited, but they cannot be finished because you will find a cycle before finishing any vertex on it). So, one easy way to find the cycle is to maintain the stack along with a dfs (vector or stack, either global or passed by reference). When you find a visited neighbor, iterate from the back of the stack until you reach that visited node, and put all the vertices you iterated on in some vector, representing the cycle.
Thanks Noam! For future reference: the iteration process in the stack after you find a visited neighbour is a parallel process to the main DFS.
Sorry. My answer is wrong as I got the wrong definition of a cycle.
In an undirected graph, all nodes in the same connected component are in a cycle.
I'm not sure that's right. Consider an undirected graph that is a chain/linked list. They are all part of the same connected component, but how is there a cycle?
https://cp-algorithms.com/graph/finding-cycle.html this may help
any one go idea how to do it usign bfs in undirected graph?
Using BFS it is more writing work than a simple DFS but still you can do that. Just run the BFS over the nodes and when you find a backedge (an edge to already visited node) , you have found a cycle .
For printing the cycle just find the LCA (lowest common ancestor) of the nodes connected by that backedge and travel parent to parent from both the nodes to the LCA. now just connect the parts in order to find the given cycle , still i would say it is a lot easier using DFS. (For making a bit simple , don't use Binary lifting for finding the LCA)
you can try this:
include<bits/stdc++.h>
using namespace std; /*
6 5
1 2 2 5 5 1 2 3 3 4
*/
//print any cycle in directed graph
vector ans;
void dfs(int node,vector& vis,vector& pathvis,vector& temp,vector<vector>& adj){ temp.push_back(node); vis[node]=1; pathvis[node]=1;
for(auto it:adj[node]){ if(!vis[it]){ dfs(it,vis,pathvis,temp,adj); } else{ if(pathvis[it]){ if(ans.size()==0){ int stop=it; while(stop!=temp.back()){ ans.push_back(temp.back()); temp.pop_back(); } ans.push_back(temp.back()); reverse(ans.begin(),ans.end()); return; return; } } } } temp.pop_back(); pathvis[node]=0; return;}
int main(){ int n,e; cin>>n>>e;
vector<vector<int>> adj(n); for (int i = 0; i <e; i++) { int u,v; cin>>u>>v; adj[u].push_back(v); /* code */ } vector<int> vis(n,0); vector<int> pathvis(n,0); vector<int> temp; for (int i = 0; i <n; i++) { if(!vis[i]){ dfs(i,vis,pathvis,temp,adj); if(ans.size()!=0){ break; } } /* code */ } if(ans.size()==0){ cout<<-1<<endl; } else{ ans.push_back(ans[0]); for(auto it:ans){ cout<<it<<" "; } }}
Hello ! You can call a dfs and use a counter variable whenever you reach a node mark the value of the counter for the particular node . Maintain an answer array which will be passed by reference whenever you call a dfs use push_back() and pop_back() to maintain it , when the condition for the graph is met the counter variables will tell you the length of the cycle and the answer array will have all the nodes in order . Return from the dfs and print the answer.