detect cycle in directed graph & un-directed graph


  • 0
    F
    
    
    /**
    Undirected Graph : for every visited vertex 'v', if there is an adjacent ‘u’ such that u is already visited and u is not parent of v, then there is a cycle in graph.
    Directed Graph : There is a cycle in a graph only if there is a back edge 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.
    **/
    
    
    /*** 有向图中检测环  **/
    
    // This function is a variation of DFSUytil() in http://www.geeksforgeeks.org/archives/18212
    bool 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/18212
    bool 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;
    }
    
    // 使用3种颜色数组用来检测环
    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;
    }
    
    /*** 无向图中检测环  **/
    // A recursive function that uses visited[] and parent to detect
    // cycle in subgraph reachable from vertex v.
    bool Graph::isCyclicUtil(int v, bool visited[], int parent)
    {
        // Mark the current node as visited
        visited[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 an adjacent is not visited, then recur for that adjacent
            if (!visited[*i])
            {
               if (isCyclicUtil(*i, visited, v))
                  return true;
            }		
            // 访问过的点并且不是当前点的父亲节点
            // If an adjacent is visited and not parent of current vertex,
            // then there is a cycle.
            else if (*i != parent)
               return true;
        }
        return false;
    }
     
    // Returns true if the graph contains a cycle, else false.
    bool Graph::isCyclic()
    {
        // Mark all the vertices as not visited and not part of recursion
        // stack
        bool *visited = new bool[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;
     
        // Call the recursive helper function to detect cycle in different
        // DFS trees
        for (int u = 0; u < V; u++)
            if (!visited[u]) // Don't recur for u if it is already visited
              if (isCyclicUtil(u, visited, -1))
                 return true;
     
        return false;
    }
    
    
    // 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’s list.
    }
     
    
    /** DFS of a graph **/
    /** if the graph is connected **/
    
    void Graph::DFSUtil(int v, bool visited[])
    {
        // Mark the current node as visited and print it
        visited[v] = true;
        cout << v << " ";
     
        // 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])
                DFSUtil(*i, visited);
    }
     
    // DFS traversal of the vertices reachable from v. It uses recursive DFSUtil()
    void Graph::DFS(int v)
    {
        // Mark all the vertices as not visited
        bool *visited = new bool[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;
     
        // Call the recursive helper function to print DFS traversal
        DFSUtil(v, visited);
    }
    
    /** DFS of a graph **/
    /** if the graph is composed of multiple connected components **/
    void Graph::DFSUtil(int v, bool visited[])
    {
        // Mark the current node as visited and print it
        visited[v] = true;
        cout << v << " ";
     
        // 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])
                DFSUtil(*i, visited);
    }
     
    // The function to do DFS traversal. It uses recursive DFSUtil()
    void Graph::DFS()
    {
        // Mark all the vertices as not visited
        bool *visited = new bool[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;
     
        // Call the recursive helper function to print DFS traversal
        // starting from all vertices one by one
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                DFSUtil(i, visited);
    }
    
    /** BFS of a grapth **/
    
    void Graph::BFS(int s)
    {
        // Mark all the vertices as not visited
        bool *visited = new bool[V];
        for(int i = 0; i < V; i++)
            visited[i] = false;
     
        // Create a queue for BFS
        list<int> queue;
     
        // Mark the current node as visited and enqueue it
        visited[s] = true;
        queue.push_back(s);
     
        // 'i' will be used to get all adjacent vertices of a vertex
        list<int>::iterator i;
     
        while(!queue.empty())
        {
            // Dequeue a vertex from queue and print it
            s = queue.front();
            cout << s << " ";
            queue.pop_front();
     
            // Get all adjacent vertices of the dequeued vertex s
            // If a adjacent has not been visited, then mark it visited
            // and enqueue it
            for(i = adj[s].begin(); i != adj[s].end(); ++i)
            {
                if(!visited[*i])
                {
                    visited[*i] = true;
                    queue.push_back(*i);
                }
            }
        }
    }
    
    /** detect cycle using the DFS method **/
    
    // This function is a variation of DFSUytil() in http://www.geeksforgeeks.org/archives/18212
    bool 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/18212
    bool 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;
    }

  • 0

    @fight.for.dream is it an interview question given in Google?


  • 0

    Wow, long code.. :stuck_out_tongue: This code is suspiciously similar to http://www.geeksforgeeks.org/detect-cycle-in-a-graph/ and http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

    I was just wondering, in case of Undirected graphs can't we simply use Disjoint Set Union policy based structures to keep track of connected components? Two different unprocessed elements having same parents would mean a cycle exists.


  • 0

    @babhishek21 yes, right


  • 0
    I

    @fight-for-dream was this for onsite?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.