BFS(Topological Sort) and DFS(Finding cycle) by C++


  • 42

    1. BFS(Topological Sort)

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        vector<unordered_set<int>> matrix(numCourses); // save this directed graph
        for(int i = 0; i < prerequisites.size(); ++ i)
            matrix[prerequisites[i][1]].insert(prerequisites[i][0]);
        
        vector<int> d(numCourses, 0); // in-degree
        for(int i = 0; i < numCourses; ++ i)
            for(auto it = matrix[i].begin(); it != matrix[i].end(); ++ it)
                ++ d[*it];
        
        for(int j = 0, i; j < numCourses; ++ j)
        {
            for(i = 0; i < numCourses && d[i] != 0; ++ i); // find a node whose in-degree is 0
            
            if(i == numCourses) // if not find
                return false;
            
            d[i] = -1;
            for(auto it = matrix[i].begin(); it != matrix[i].end(); ++ it)
                -- d[*it];
        }
        
        return true;
    }
    

    2. DFS(Finding cycle)

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        vector<unordered_set<int>> matrix(numCourses); // save this directed graph
        for(int i = 0; i < prerequisites.size(); ++ i)
            matrix[prerequisites[i][1]].insert(prerequisites[i][0]);
        
        unordered_set<int> visited;
        vector<bool> flag(numCourses, false);
        for(int i = 0; i < numCourses; ++ i)
            if(!flag[i])
                if(DFS(matrix, visited, i, flag))
                    return false;
        return true;
    }
    bool DFS(vector<unordered_set<int>> &matrix, unordered_set<int> &visited, int b, vector<bool> &flag)
    {
        flag[b] = true;
        visited.insert(b);
        for(auto it = matrix[b].begin(); it != matrix[b].end(); ++ it)
            if(visited.find(*it) != visited.end() || DFS(matrix, visited, *it, flag))
                return true;
        visited.erase(b);
        return false;
    }

  • 0
    B
    This post is deleted!

  • 0
    S

    for bool DFS(), below can be added at the beginning to avoid unnecessary loop.

    if (flag[b] == true)
    	return false;
    

  • 0

    Yes, that's right. Thanks.


  • 22

    My accepted 264ms topological sort solution using a queue to save the nodes which indegree is equal to 0:

    class Solution {
    public:
    	bool canFinish(int numCourses, std::vector<std::pair<int, int> > &prerequisites) {
    		std::vector<std::unordered_set<int> > need(numCourses);
    		for (std::size_t i = 0; i != prerequisites.size(); ++i)
    			need[prerequisites[i].second].insert(prerequisites[i].first);
    		std::vector<int> indegree(numCourses);
    		for (int i = 0; i != numCourses; ++i)
    			for(auto it = need[i].begin(); it != need[i].end(); ++it)
    				++indegree[*it];
    		std::queue<int> zeros;
    		for (int i = 0; i != numCourses; ++i)
    			if (indegree[i] == 0)
    				zeros.push(i);
    		while (!zeros.empty()) {
    			int seq = zeros.front();
    			zeros.pop();
    			for (auto it = need[seq].begin(); it != need[seq].end(); ++it)
    				if (--indegree[*it] == 0)
    					zeros.push(*it);
    			--numCourses;
    		}
    		return numCourses == 0;
    	}
    };

  • 0
    T

    Hi, Thank you for your code contribution. You DFS part of the code can be made work using only the vector<bool> flag and removing the unordered_set<int> visited. I tried so but the code ran slower (700 ms instead of 300 ms). can you explain why unordered set was used? thank.


  • 0

    Hi, totolipton. I am not the author of the code. But according to my understanding, flag is to store all the visited nodes after all the DFS visit (each DFS visit starts from an unvisited node and tries to go as deep as possible) while visited is to store the nodes during the current DFS. Once the current DFS visit is done, we need to erase the starting node from it to correctly start the next check for cycle.

    In fact, I am curious about how you could make the code work without using two separate records for the visited nodes.


  • 1
    M

    I just finish the Course Schedule II problem and get a neat and simple answer.
    I make a simple version for this Course Schedule problem. Running time is about 264ms.

    class Solution {
        vector<vector<int>> list;
        unordered_set<int> visited;
        unordered_set<int> cycle;
        bool isCycle=false;
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            list.assign(numCourses, vector<int>());
            for(int i=0; i<prerequisites.size(); i++)
            {
                list[prerequisites[i].second].push_back(prerequisites[i].first);
            }
            for(int j=0; j<numCourses; j++)
            {
                if(visited.count(j)<1) dfs(j);
                if(isCycle) return false;    
            }
            return true;
        }
        void dfs(int j)
        {
            cycle.insert(j);
            visited.insert(j);
            for(int k=0; k<list[j].size(); k++)
            {
                if(cycle.count(list[j][k])>0) isCycle=true;  //use hashset to detect the cycle
                if(visited.count(list[j][k])<1) dfs(list[j][k]);
            }
            cycle.erase(j);
        }
    };
    

  • 0
    Q

    OO design, hope it can help.

    class Graph{
    public:
        Graph(int V);
        void addEdge(int u, int v);
        bool detectCycleUtil(vector<bool> & visited, vector<bool> & recStack, int u);
        bool detectCycle();
    private:
        int V;
        vector<vector<int> > adj;
    };
    
    Graph::Graph(int V){
        this->V = V;
        adj.resize(V);
    }
    
    void Graph::addEdge(int u, int v){
        adj[u].push_back(v);
    }
    
    bool Graph::detectCycleUtil(vector<bool> & visited, vector<bool> & recStack, int u){
        visited[u] = true;
        recStack[u] = true;
        for(auto itr=adj[u].begin(); itr!=adj[u].end(); ++itr){
            int v = *itr;
            if(recStack[v]==true)
                return true;
            if(visited[v]==false && detectCycleUtil(visited, recStack, v))
                return true;
        }
        recStack[u] = false;
        return false;
    }
    bool Graph::detectCycle(){
        vector<bool> visited(V, false);
        vector<bool> recStack(V, false);
        for(int i=0; i<V; i++){
            if(visited[i]==false){
                if(detectCycleUtil(visited, recStack, i))
                    return true;
            }
        }
        return false;
    }
    
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            Graph graph(numCourses);
            for(int i=0, len=prerequisites.size(); i<len; i++)
                graph.addEdge(prerequisites[i].second, prerequisites[i].first);
            return !graph.detectCycle();        
        }
    };

  • 0
    S

    The BFS solution is nice, but looks like it takes O(V^2 + E) to complete as the algorithm need to search for indegree = 0 for each vertex. I think we can use heap to improve the lookup process, but still it takes O(ElgV), while DFS takes O(V+E) that seems with much better performance, what do you think?


  • 0
    F

    here is a less messy solution without the visited set

    class Solution {
    public:
    enum class NStatus {UNVISITED, TEMPVISITED, VISITED};

    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
    	vector<vector<int>> matrix(numCourses);
    	for (int i = 0; i < prerequisites.size(); ++i)
    		matrix[prerequisites[i].second].push_back(prerequisites[i].first);
    
    	vector<NStatus> flag(numCourses, NStatus::UNVISITED);
    	for (int i = 0; i < numCourses; ++i)
    		if (flag[i]!=NStatus::VISITED)
    			if (hasCycle(matrix, i, flag))
    				return false;
    	return true;
    }
    
    bool hasCycle(vector<vector<int>>& matrix, int i, vector<NStatus>& flag) {
    	if (flag[i] == NStatus::TEMPVISITED)
    		return true;
    	flag[i] = NStatus::TEMPVISITED;
    	for (int j: matrix[i]) {
    		if ((flag[i] != NStatus::VISITED) && hasCycle(matrix, j, flag))
    			return true;
    	}
    	flag[i] = NStatus::VISITED;
    	return false;
    }
    

    };

    check topological search on wikipedia and Tarjan algorithm


  • 0
      Detailed comments for your implementation based on BFS. Welcome optimizing ideas !!! 
    
    
       class Solution {
        public:
            bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
                vector<unordered_set<int>> matrix(numCourses, unordered_set<int>());
                /*** construct the directed graph : (1, 0) means edge:0->1  ***/
                for(int i=0; i<prerequisites.size(); i++)
                    matrix[prerequisites[i].second].insert(prerequisites[i].first);
                /*** statistic all the in-degree of all the vertex ***/    
                vector<int> d(numCourses, 0);
                for(int i=0; i<numCourses; i++)
                    for(auto it = matrix[i].begin(); it!=matrix[i].end(); it++){
                        d[*it]++;
                    }
                
                /*** topological sort ***/   
                for(int j=0, i; j<numCourses; ++j){
                    /*** find the node with in-degree=0 ***/
                    for(i=0; i<numCourses && d[i]!=0; i++);
                    if(i==numCourses)   return false;
                    d[i]=-1;  /*** set d[i]=-1 means delete the node ***/
                    for(auto it=matrix[i].begin(); it!=matrix[i].end(); it++) d[*it]--;
                }
                return true;
            }
        };

Log in to reply
 

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