leetcode: Clone Graph

问题描述：

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

 

OJ's undirected graph serialization:

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 #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. 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
         / \
         \_/

 

原问题链接：https://leetcode.com/problems/clone-graph/

 

问题分析

　　在这个问题里，要对一个图进行克隆。既然要对一个图进行克隆的话，肯定要想法子遍历整个图，并将图里面每个节点都访问到并且克隆到新的图里面才行。所以这个问题里就是要考虑怎么来遍历这个图并且复制每个节点。

　　对于图的遍历来说，我们可以采用深度优先遍历或者广度优先遍历。至少看起来随便用哪种都可以。现在主要的问题是在遍历的时候，该怎么复制节点呢？ 对于一个图来说，它一个节点可能就对应有多个邻接节点，就算我们碰到这个节点的时候将这个节点的值作为参数新构造一个节点，这还不是完整的克隆。因为它的那些邻接节点都还要设置。可是在刚开始都没遍历到那些节点呢，没法一开始就把所有的节点都设上。

　　这里我们可以采用一个map，保存有原来图中访问过的节点以及对应的新图中要克隆的节点。这样我们对于节点就构成了一个一一对应的关系。在图遍历的过程中可能会碰到前面访问过的节点，这样可以通过这个map来判断了。

　　假设我们采用广度优先遍历的方式来处理。在碰到一个节点之后，将它所有邻接节点都依次取出来，如果在map里已经找到了对应的元素，就将这个元素加到它对应节点的邻接节点列表里。否则就新建一个节点，并将这个新节点加入到对应节点的邻接节点列表里。当然，这个新节点也要加入到map和队列中。按照这样一个顺序一直遍历结束。

　　详细的代码实现如下：

 

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) return null;
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        queue.add(node);
        UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
        map.put(node, copy);
        while(!queue.isEmpty()) {
            UndirectedGraphNode temp = queue.remove();
            copy = map.get(temp);
            for(UndirectedGraphNode item : temp.neighbors) {
                if(map.containsKey(item)) {
                    copy.neighbors.add(map.get(item));
                } else {
                    UndirectedGraphNode newNode = new UndirectedGraphNode(item.label);
                    map.put(item, newNode);
                    copy.neighbors.add(newNode);
                    queue.add(item);
                }
            }
        }
        return map.get(node);
    }
}