logo
down
shadow

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


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;
    for (i = adj[u].begin(); i != adj[u].end(); ++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 : facebook icon twitter icon
How to find of what vertices is made cycle in undirected graph if there is only one cycle in graph?

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?

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

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?

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

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;
}
Related Posts Related Posts :
  • Casting the sum of some variables to a pointer and then to an integer again
  • What's the easiest way to send 802.11 frames using C?
  • C Opening a file to check if it is Binary, if so print it is binary
  • why 2 different strings have the same address in C?
  • when I try to end an event controlled loop in c it takes two inputs?
  • adding string to character array at specific position giving buffer overflow in c programming
  • C - Separating string using other delimiters?
  • Rounding down a floating point number to an integer value without a floor function in C
  • Why does the computer ignore my program?
  • Pointer calculation in Linux Kernel allocation implementation
  • conflicting types for s32_t in c code for STM32F7xx
  • Getting error in AVL tree
  • LD_PRELOAD and linkage
  • For loop skipping numbers in C
  • C code - Why the output returned unexpected value in my code?
  • C - can variate location be promoted?
  • Signal SIGSEGV recieved: vfprintf.c: No such file or directory?
  • Does Posix thread ID have an one-to-one relation with linux thread ID?
  • C - fgets doesnt wait for input when initializing pointer
  • I cannot perform data validation on my four arrays properly.
  • How do I fix this segmentation fault in my c code
  • How to use pointer to split the string into two strings? C language
  • Knuth List Insertion Method in C
  • Tons of error in Visual Studio 2017 with GetUserNameEx at compile time
  • Invalid conversion of char to float, different codes and no good results
  • Why doesn't my code for checking if a word is a palindrome work?
  • My program compiles and when ran, it doesn't give me the input i put in
  • Memory mapped file cannot be closed without un-mapping, since it's still referenced
  • Why is this simple program giving me seemingly incorrect output?
  • second printf not working when using a variable C-programming
  • Shared memory variable in c
  • Linked List and Pointers in C
  • Counting Character usage in text file? C
  • C: Why does assigning a 2D array of ints to an int** cause CLION to highlight the line?
  • How does fwrite work?
  • Why is my http server printing out the same bytes? (C)
  • The following code doesn't stop looping
  • Strcmp gives segmentation Fault
  • Segmentation fault: 1902 vfscanf.c: No such file or directory
  • Mutex - counting occurrences of a char in files using threads
  • Returning arrays in C instead of switch statements, nested set of values
  • Trying to pass addresses to simple variables to a function (pointers & loops) In C
  • Recursively list directories in C on Linux
  • Math operation in the test expression of the `for` loop - perfomance, optimisation
  • what is the difference between extern char **environ and extern char *environ[]
  • Is it possible to bind a socket to 2 adresses in c?
  • error when compiling testfiles from installed c-algorithms library
  • Count alternating up / down sequences
  • ISR documentation with doxygen
  • How to solve the sum of three digit numbers,with how to calculate the second number
  • Recursion C image compressor algorithm
  • Unix system programming: get a network identifier to be passed to getaddrinfo
  • misaligned address access crash on linux wifi drivers on arc platform
  • Having a character appear repeated times in an array and score counts.
  • Given a number A(=2^N), how to get the N?
  • Reading Hex from an file
  • Realloc affecting fgets
  • Run C server and client files in CLion at the same time
  • How to check last character in command line arguements?
  • How to seperate user input word delimiter as space using strtok
  • shadow
    Privacy Policy - Terms - Contact Us © voile276.org