Clone Graph

Problem: Clone Graph

The problem is a depth-first search or breadth-first search problem. We conventionally use stack or recursion to solve DFS and queue to solve BFS.

Code in Python:

from collections import deque

# Definition for a undirected graph node
# class UndirectedGraphNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: UndirectedGraphNode
        :rtype: UndirectedGraphNode
        """
        if not node:
            return
        res = UndirectedGraphNode(node.label)
        dict = {node: res}
        queue = deque([node])
        while queue:
            current = queue.popleft()
            for n in current.neighbors:
                if n not in dict:
                    currentNode = UndirectedGraphNode(n.label)
                    dict[current].neighbors.append(currentNode)
                    dict[n] = currentNode
                    queue.append(n)
                else:
                    dict[current].neighbors.append(dict[n])
        return res

To avoid duplicate nodes, we can maintain a dict to store all visited nodes and its related copied node. FYI, more detailed solutions are provided at this page.