LeetCode: Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

---

We can use BFS to search the graph can clone it at the same time. A map can be used to store those nodes that are already cloned.

C++ Code:

/*
 * func: clone_graph_helper
 * goal: helper function to perform BFS
 * @param node: current node to be cloned
 * @param visited: node already existed in the new graph
 * return: newly cloned node
 */
UndirectedGraphNode *clone_graph_helper(UndirectedGraphNode *node, unordered_map<int, UndirectedGraphNode*> &visited){
    UndirectedGraphNode *new_node = new UndirectedGraphNode(node->label);
    visited[node->label] = new_node;
    for(int i = 0; i < node->neighbors.size(); ++i){
        if(visited.find(node->neighbors[i]->label) != visited.end()){
            new_node->neighbors.emplace_back(visited[node->neighbors[i]->label]);
        }else{
            new_node->neighbors.emplace_back(clone_graph_helper(node->neighbors[i], visited[node->neighbors[i]->label]));
        }
    }
    
    return new_node;
}

/*
 * func: clone_graph
 * goal: clone a undirected graph
 * @param node: a start node
 * return: a cloned start node
 */
UndirectedGraphNode *clone_graph(UndirectedGraphNode *node){
    if(node == nullptr){
        return nullptr;
    }
    unordered_map<int, UndirectedGraphNode*> visited;
    UndirectedGraphNode* new_node = clone_graph_helper(node, visited);
    return new_node;
}

Python Code:

# func: clone graph
# @param node: start node
# @return: new start node
def clone_graph(node):
    if not node:
        return None

    visited = {}
    def clone_graph_helper(start):
        new_node = UndirectedGraphNode(start.label)
        visited[start.label] = new_node
        for neighbor in start.neighbors:
            if neighbor.label in visited:
                new_node.neighbors.append(visited[neighbor.label])
            else:
                new_node.neighbors.append(clone_graph_helper(neighbor))
        return new_node

    return clone_graph_helper(node)