Python iterative BFS/DFS


  • 1
    Z

    Two scans, first round clone node, second round clone paths.

    The BFS with for-loop instead of queue was from Stefan :P

    def cloneGraph(self, node):
        ## BFS
        dic = {}
        stack = [node] if node else []
        for i in stack:
            if i not in dic:
                dic[i] = UndirectedGraphNode(i.label)
            stack.extend([j for j in i.neighbors if j not in dic])
        for i in dic:
            for j in i.neighbors:
                dic[i].neighbors.append(dic[j])
        return dic[node] if node else node
    
        ## DFS
        dic = {}
        stack = [node] if node else []
        while stack:
            i = stack.pop()
            if i not in dic:
                dic[i] = UndirectedGraphNode(i.label)
            stack.extend([j for j in i.neighbors if j not in dic])
        for i in dic:
            for j in i.neighbors:
                dic[i].neighbors.append(dic[j])
        return dic[node] if node else node

  • 0
    S

    brilliant, I was doing one loop instead, but much lengthy coding.


Log in to reply
 

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