C++ dfs (backtracking) and bfs (indegree) methods


  • 6
    M

    First method is dfs. Idea is to start from each node in graph, go down every path (using its adjacency list) and mark each node along path. If you see a node in a path again (already marked) then there is a cycle in graph. For this algorithm to work in O(V+E) time (V:vertices, E:edges), flag each visited node and do not start a path using flagged nodes. This is because paths started from flagged nodes have already been checked during previous dfs calls.

    Second method is bfs. First compute the indegree array (how many edges toward a node). Use a stack to push all nodes with indegree 0. Start from a node on the stack and subtract by 1 of all the nodes on its adjacency list. If after subtraction, the node has indegree 0, push it onto stack. Do this recursively for all nodes on stack until no nodes are on stack (you pop a node after subtracting by 1 of all nodes on its adjacency list). If there is at least one node that is never pushed on stack, the graph has a cycle. Too see why draw a digraph with a cycle between two nodes (1->2, 2->1) and for all other nodes draw no cycle. Follow this algorithm you will see the indegree array will be all 0 except for node 1 and 2, which both have indegree 1.

    I think both algorithms run in O(V+E) time and O(V) space I do not take the adjacency list into account)

    The codes:

    DFS:

    class Solution {
    public:
        bool canFinish(int num, vector<vector<int>>& pre) {
            if(num==0) return true;
            /*
            * "mark" is to mark nodes in a "path". If a node is marked and you 
            * see it again in a "path", the graph has a cycle.
            * "flag" is to mark visited nodes in a graph. Once a node is flaged 
            * it will not be used as a starting point to search for cycles 
            * (i.e. it is for backtracking)
            * "nei" is the adjacency list. The problem gives us the "edge list"
            * it is better to convert it to adjacency list first
            */
            bool mark[num]={false}; 
            bool flag[num]={false};
            vector<vector<int>> nei(num);
            for(int i=0; i<pre.size(); i++) 
                nei[pre[i][1]].push_back(pre[i][0]);
            for(int i=0; i<num; i++) {
                if(!flag[i]) {
                    if(hasCycle(i,mark,flag,nei)) return false;
                }
            }
            return true;
        }
    private:
        /*
        * \return true; if there is a cycle in graph
        */
        bool hasCycle(int cur, bool mark[], bool flag[], const vector<vector<int>>& nei) {
            flag[cur]=true;
            for(int i=0; i<nei[cur].size();i++) {
                int neiIndex = nei[cur][i];
                if(mark[neiIndex]) return true;
                mark[neiIndex]=true;
                if(hasCycle(neiIndex,mark,flag,nei)) return true;
                mark[neiIndex]=false;
            }
            return false;
        }
    };
    

    BFS:

    class Solution {
    public:
        bool canFinish(int num, vector<vector<int>>& pre) {
            if(num==0) return true;
            
            vector<vector<int>> adj(num);
            for(int i=0; i<pre.size(); i++) // convert edge list to adjacency list
                adj[pre[i][1]].push_back(pre[i][0]);
            
            int indegree[num]={0}; 
            for(int i=0; i<num; i++) // compute the indegree array
                for(int j=0; j<adj[i].size(); j++)
                    indegree[adj[i][j]]++;
            
            stack<int> in0; // stores nodes with indegree 0
            for(int i=0; i<num; i++) 
                if(indegree[i]==0) in0.push(i);
            
            int count = 0;
            while(!in0.empty()) {
                int index = in0.top();
                in0.pop();
                count++;
                for(int i=0; i<adj[index].size(); i++)
                    if(--indegree[adj[index][i]]==0) in0.push(adj[index][i]);
            }
            return count == num;
        }
    
    };

Log in to reply
 

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