Clone Graph

Question

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains alabel (int) and a list (List[UndirectedGraphNode]) of itsneighbors. There is an edge between the given node and each of the nodes in its neighbors.

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

How we serialize an undirected graph:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

  1
 / \
/   \
0 --- 2
    / \
    \_/

Have you met this question in a real interview? Yes

Example return a deep copied graph.

Tags Breadth First Search Facebook

Analysis

本题是Graph相关的基础问题，图的遍历主要有两种方法：BFS，DFS，也就是广度优先搜索和深度优先搜索。

Breadth-first Search

Wikipedia: “In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. Compare BFS with the equivalent, but more memory-efficient Iterative deepening depth-first search and contrast with depth-first search.”

这是一种对图的遍历方法，对于一个节点来说先把所有neighbors都检查一遍，再从 第一个neighbor开始，循环往复。

由于BFS的这个特质，BFS可以帮助寻找最短路径。

通常BFS用queue+循环实现。

Depth-first Search

Wikipedia: “Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.”

通常来说简便的DFS写法是用递归，如果非递归的话就是栈套迭代，思想是一样的。

思路1：使用BFS，先将头节点入queue，每一次queue出列一个node，然后检查这个node的所有的neighbors，如果没visited过，就入队，并更新neighbor。

思路2：使用DFS，可以分为迭代和循环两种方式，后者需要利用stack。

Solution

BFS - breadth first search, non-recursive

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        UndirectedGraphNode head = new UndirectedGraphNode(node.label);
        hm.put(node, head);
        queue.add(node);

        while (!queue.isEmpty()) {
            UndirectedGraphNode currentNode = queue.remove();
            for (UndirectedGraphNode neighbor : currentNode.neighbors) {
                if (!hm.containsKey(neighbor)) {
                    queue.add(neighbor);
                    UndirectedGraphNode newNeighbor = new UndirectedGraphNode(neighbor.label);
                    hm.put(neighbor, newNeighbor);
                }
                hm.get(currentNode).neighbors.add(hm.get(neighbor));
            }
        }

        return head;
    }
}

DFS - depth first search, non-recursive

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null)
            return null;

        HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        LinkedList<UndirectedGraphNode> stack = new LinkedList<UndirectedGraphNode>();
        UndirectedGraphNode head = new UndirectedGraphNode(node.label);
        hm.put(node, head);
        stack.push(node);

        while(!stack.isEmpty()){
            UndirectedGraphNode curnode = stack.pop();
            for(UndirectedGraphNode aneighbor: curnode.neighbors){//check each neighbor
                if(!hm.containsKey(aneighbor)){//if not visited,then push to stack
                    stack.push(aneighbor);
                    UndirectedGraphNode newneighbor = new UndirectedGraphNode(aneighbor.label);
                    hm.put(aneighbor, newneighbor);
                }

                hm.get(curnode).neighbors.add(hm.get(aneighbor));
            }
        }

        return head;
    }
}

DFS Recursive

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        return cloneGraph(node, new HashMap<>());
    }

    private UndirectedGraphNode cloneGraph(UndirectedGraphNode node, 
            Map<UndirectedGraphNode, UndirectedGraphNode> cloneMap) {

        UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
        cloneMap.put(node, clone);

        for (UndirectedGraphNode neighbor : node.neighbors) {
            UndirectedGraphNode neighborClone = cloneMap.get(neighbor);
            if (neighborClone != null) {
                clone.neighbors.add(neighborClone);
            }
            else {
                clone.neighbors.add(cloneGraph(neighbor, cloneMap));
            }
        }

        return clone;
    }
}

Reference

• Clone Graph leetcode java（DFS and BFS 基础）