C RUBY-ON-RAILS MYSQL ASP.NET DEVELOPMENT RUBY .NET LINUX SQL-SERVER REGEX WINDOWS ALGORITHM ECLIPSE VISUAL-STUDIO STRING SVN PERFORMANCE APACHE-FLEX UNIT-TESTING SECURITY LINQ UNIX MATH EMAIL OOP LANGUAGE-AGNOSTIC VB6 MSBUILD

# How to find if a graph contains a cycle using a recursive DFS?

By : Bline Emilie
Date : November 21 2020, 03:00 PM
I hope this helps . You are correct that there is no way to tell if the visited node has already been visited or if was visited as part of current traversal.
One approach would be to maintain a array of vertices that can hold three states instead of the two which we already have.
code :
``````// Recursive function to find if there is back edge
// in DFS subtree tree rooted with 'u'
bool Graph::DFSUtil(int u, int color[])
{
// GRAY :  This vertex is being processed (DFS
//         for this vertex has started, but not
//         ended (or this vertex is in function
//         call stack)
color[u] = GRAY;

// Iterate through all adjacent vertices
list<int>::iterator i;
{
int v = *i;  // An adjacent of u

// If there is
if (color[v] == GRAY)
return true;

// If v is not processed and there is a back
// edge in subtree rooted with v
if (color[v] == WHITE && DFSUtil(v, color))
return true;
}

// Mark this vertex as processed
color[u] = BLACK;

return false;
}

// Returns true if there is a cycle in graph
bool Graph::isCyclic()
{
// Initialize color of all vertices as WHITE
int *color = new int[V];
for (int i = 0; i < V; i++)
color[i] = WHITE;

// Do a DFS traversal beginning with all
// vertices
for (int i = 0; i < V; i++)
if (color[i] == WHITE)
if (DFSUtil(i, color) == true)
return true;

return false;
}
``````

Share :

## How to find of what vertices is made cycle in undirected graph if there is only one cycle in graph?

By : Israel Machovec
Date : March 29 2020, 07:55 AM
I hope this helps you . If i'm right, then parent[] is an array (parent[i] is the number of the node that you vivted straight before you visited the i-th one).
Then you know that if the graph contains the cycle (you visit a node you have already visited), you know at least one node in the cycle (suppose its the k-th one). In this case, the parent[k] node also belongs to the cycle, and parent[parent[k]], and so on.
code :
``````#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

vector <int> state;
vector <vector <int> > ls; //graph
vector <int> parent;
bool t = 1;
int theNodeInTheCycle;

void dfs(int x)
{
state[x] = 1;
for(int j = 0; j < ls[x].size(); j++)
{
if(state[ls[x][j]] == 1 && parent[x] != ls[x][j])
{
parent[ls[x][j]] = x;
theNodeInTheCycle = ls[x][j]; //ls[x][j] belongs to the cycle since state[ls[x][j]]==1
t = 0;
}
if(state[ls[x][j]] == 0)
{
parent[ls[x][j]] = x;
dfs(ls[x][j]);
}
}
}

vector <int> GetCycle ()
{
vector <int> cycle;
int firstNodeInTheCycle = theNodeInTheCycle;
do
{
theNodeInTheCycle = parent[theNodeInTheCycle];
cycle.push_back (theNodeInTheCycle);
} while (theNodeInTheCycle != firstNodeInTheCycle);

reverse (cycle.begin (), cycle.end ()); //to get them in the right order
return cycle;
}

int main()
{
int n; cin>>n; //the number of nodes (from 0 to n-1)
int m; cin>>m; //the number of edges

state.resize (n);
ls.resize (n);
parent.resize (n);

for (int i = 0; i < m; ++i)
{
int a, b; cin>>a>>b;
ls[a].push_back(b);
ls[b].push_back(a);
}

for (int i = 0; i<n; ++i)
if (state[i]==0)
dfs(i);

if (t==0)
{
vector <int> cycle = GetCycle ();
for (int i = 0; i < cycle.size (); ++i)
cout<<cycle[i]<<" ";
cout<<"\n";
}
else cout<<"No cycle\n";
}
``````

## How to find if a graph has a cycle?

By : JurnalPonsel
Date : March 29 2020, 07:55 AM
may help you . Note: this answer assumes that the graph is undirected (put another way, the adjacency matrix is symmetric). For a directed graph, the answer is more complex.
You need to check the value returned from the recursive call to hasCycle(j). For example:
code :
``````if (hasCycle(j))
return true;
``````
``````public boolean hasCycle(int start)
{
vertexList[start].wasVisited = true;
for (int j = 0; j < MAX_VERTS; j++) {
if (adjMat[start][j] == 1  &&  (vertexList[j].wasVisited  ||  hasCycle(j)))
return true;
}
return false;
}
``````
``````public boolean hasCycle(int start, int parent)
{
vertexList[start].wasVisited = true;
for (int j = 0; j < MAX_VERTS; j++) {
if (j != parent  &&  adjMat[start][j] == 1  &&  (vertexList[j].wasVisited  ||  hasCycle(j, start)))
return true;
}
return false;
}
``````

## Find whether graph has a cycle

By : user2468369
Date : March 29 2020, 07:55 AM
hope this fix your issue First, I assume this is a directed graph. An undirected graph has a trivial cycle if it contains a single edge.
The only tricky part to the recursive CTE is stopping when you've hit a cycle -- so you don't get infinite recursion.
code :
``````with cte as (
select e.object_a, e.object_b, iscycle = 0
from edges e
union all
select cte.object_a, e.object_b,
(case when cte.object_a = e.object_b then 1 else 0 end) as iscycle
from cte join
edges e
on cte.object_b = e.object_a
where iscycle = 0
)
select max(iscycle)
from cte;
``````

## Detected Cycle in directed graph if the vertex is found in recursive stack-why?

By : Ataollah
Date : March 29 2020, 07:55 AM
wish of those help From a brief look, the code snippet is an implementation of depth-first search, which is a basic search technique for directed graphs; the same approach works for breadth-first search. Note that apparently this implementation works only if there is only one connected component, otherwise the test must be performed for each connected component until a cycle is found.
That being said, the technique works by choosing one node at will and starting a recursive search there. Basically, if the search discovers a node that is in the stack, there must be a cycle, since it has been previously reached.

## detect cycle in directed graph with non-recursive dfs

By : Pravin
Date : March 29 2020, 07:55 AM
I wish this helpful for you If you like an iterative approach of cycle detection with DFS, I will recommend you a little reorganized version of your code, where I write DFS in a more common manner.
code :
``````bool isCyclic(int V, vector<int> adj[]) {
vector<bool> visited (V, false);
vector<bool> on_stack (V, false);
stack<int> st;

for (int w = 0; w < V; w++) {

if (visited[w])
continue;
st.push(w);

while (!st.empty()) {
int s = st.top();

if (!visited[s]) {
visited[s] = true;
on_stack[s] = true;
} else {
on_stack[s] = false;
st.pop();
}

for (const auto &v : adj[s]) {
if (!visited[v]) {
st.push(v);
} else if (on_stack[v]) {
return true;
}
}
}
}
return false;
}
``````