Python dfs, bfs solutions with comments.


  • 25
    C
    # BFS
    def findOrder1(self, numCourses, prerequisites):
        dic = {i: set() for i in xrange(numCourses)}
        neigh = collections.defaultdict(set)
        for i, j in prerequisites:
            dic[i].add(j)
            neigh[j].add(i)
        # queue stores the courses which have no prerequisites
        queue = collections.deque([i for i in dic if not dic[i]])
        count, res = 0, []
        while queue:
            node = queue.popleft()
            res.append(node)
            count += 1
            for i in neigh[node]:
                dic[i].remove(node)
                if not dic[i]:
                    queue.append(i)
        return res if count == numCourses else []
        
    # DFS
    def findOrder(self, numCourses, prerequisites):
        dic = collections.defaultdict(set)
        neigh = collections.defaultdict(set)
        for i, j in prerequisites:
            dic[i].add(j)
            neigh[j].add(i)
        stack = [i for i in xrange(numCourses) if not dic[i]]
        res = []
        while stack:
            node = stack.pop()
            res.append(node)
            for i in neigh[node]:
                dic[i].remove(node)
                if not dic[i]:
                    stack.append(i)
            dic.pop(node)
        return res if not dic else []

  • 0
    V

    Hi. Very nice solution! But it appears to me that your dfs solution is actually a bfs solution. I don't see any recursion in your dfs.


  • 2
    C

    No, it is dfs indeed. You can implement dfs recusively but also iteratively. Explicit stack is needed If we are using iterative dfs, in the way, we are using explicit stack to simulate the calling stack in recursive dfs. Hope it's useful~


  • 0
    C

    Hi! This is an awesome solution! I am wondering if there is some way to output all the possible situation based on your solution?

    Thanks, looking forward to your reply.


  • 1
    L

    @caikehe I wouldn't say it's DFS since you're going through the neighbors and then adding into the stack. Still looks like BFS to me

     for i in neigh[node]:
                dic[i].remove(node)
                if not dic[i]:
                    stack.append(i)

  • 3
    Z

    @livelearn
    Stack(FILO) and pop() function pops out the last item in the array. Although the neighbors( "i in neigh[node]" ) are added into stack that looks like DFS, but they won't be pop out in the same order. For example, if we have "dic", "neigh" and "stack" like this:
    dic = { 3: [1,2], 4: [2,3]}, neigh = {1: [3], 2: [3, 4], 3: [4] } and stack = [0,1,2]
    1st iteration:
    node = 2, res = [2], dic = {3: [1], 4:[3]}, neigh = {1: [3], 2: [3, 4], 3: [4] } , stack = [0, 1]
    2nd iteration:
    node = 1, res[2, 1], dic = {4:[3]},neigh = {1: [3], 2: [3, 4], 3: [4] } , stack = [0, 3]
    3rd iteration:
    node = 3, res[2,1,3], dict = {}, neigh = {1: [3], 2: [3, 4], 3: [4] } , stack = [0, 4]
    // Here, node 3 is the child of node 1, and it's been taken right after node 1 since it's pop from a stack(last in first out). It means that as long as the child node meets the condition that no prerequisite is required or all the prerequisite has been taken, this child node will be added to the result and it's children will be added to the stack. So the next to be visited is node 4 -- the child of node 3.
    Thus, the final effect is still dfs, although not the normal dfs in our common sense. It's like always going to the next level through the last child (or the right most leaf if you are more familiar the tree structure), instead of the first child it reaches directly (or the left most leaf).
    It's just my thought, and I hope it makes sense. Please let me know if I made anything wrong here. :)


  • 0
    S

    Wonder how does it detect or behave in 'cycle'...


  • 0
    B

    @sha256pki If the tree contains cycle, the returned dictionary dic would not be empty. Therefore the dfs function will return []


  • 1
    Q
    This post is deleted!

  • 0
    2

    nice solution, however I think dic[i] should be the indegree of the node i, then computing will be faster !!

    class Solution(object):
        def findOrder(self, numCourses, prerequisites):
            # dic[i] is the indegree of the node i,  computing will be faster
            dic  = [0 for i in xrange(numCourses)];
            neigh = collections.defaultdict(set)
            for i, j in prerequisites:
                dic[i] += 1;
                neigh[j].add(i)
            stack  = [i for i in xrange(numCourses) if dic[i] == 0];
            res = []
            while stack:
                node = stack.pop()
                res.append(node)
                for i in neigh[node]:
                    dic[i] -= 1
                    if dic[i] == 0:
                        stack.append(i)
            for i in xrange(numCourses):
                if dic[i] > 0:
                    return [];
            return res;
    

  • 0
    J

    what's the time complexity?
    I don't think this solution is efficient


  • 0
    L

    Great solution. I found it to be very intuitive. Here is a cleaned up version.

        def findOrder(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: List[int]
            """
    
            g = {i:set() for i in range(0, numCourses)}
            g_inv = collections.defaultdict(set)
            for i, j in prerequisites:
                g[i].add(j)
                g_inv[j].add(i)
    
            q = queue.Queue()
            for course in g:
                if not g[course]:
                    q.put(course)
    
            topo_sort = []
            while not q.empty():
                front = q.get()
                topo_sort.append(front)
    
                for elm in g_inv[front]:
                    g[elm].remove(front)
                    if not g[elm]:
                        q.put(elm)
    
            return topo_sort if len(topo_sort) == numCourses else []
    

Log in to reply
 

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