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

Leetcode里關于圖的題其實并不多，這道題就是其中之一。DFS深度優先搜索和BFS廣度優先搜索都可以做，遍歷完原圖的所有節點。這道題的難點在于neighbour關系的拷貝：原圖中某一個點跟一些點具有neighbour關系，那么該點的拷貝也要與上述那些點的拷貝具有neighbour關系。那么，就需要很靈活地通過一個點訪問該點的拷貝，最好的辦法就是把該點與該點的拷貝存入一個HashMap。這樣做還有一個好處，就是幫我們剩下了一個visited數組，我們可以用這個HashMap來知道哪些點我是訪問過的。

方法是用BFS做的：

 1 /** 2  * Definition for undirected graph. 3  * class UndirectedGraphNode { 4  *     int label; 5  *     List<UndirectedGraphNode> neighbors; 6  *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } 7  * }; 8  */ 9 public class Solution {10     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {11         if (node == null) return null;12         HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();13         LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();14         queue.offer(node);15         UndirectedGraphNode copy = new UndirectedGraphNode(node.label);16         map.put(node, copy);17         while (!queue.isEmpty()) {18             UndirectedGraphNode cur = queue.poll();19             for (int i=0; i<cur.neighbors.size(); i++) {20                 if (!map.containsKey(cur.neighbors.get(i))) {21                     queue.offer(cur.neighbors.get(i));22                     UndirectedGraphNode neighborCopy = new UndirectedGraphNode(cur.neighbors.get(i).label);23                     map.put(cur.neighbors.get(i), neighborCopy);24                 }25                 map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));26             }27         }28         return map.get(node);29     }30 }

網上看了別人的解法：

用Stack寫的DFS方法：

 1 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { 2     if(node == null) 3         return null; 4     LinkedList<UndirectedGraphNode> stack = new LinkedList<UndirectedGraphNode>(); 5     HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); 6     stack.push(node); 7     UndirectedGraphNode copy = new UndirectedGraphNode(node.label); 8     map.put(node,copy); 9     while(!stack.isEmpty())10     {11         UndirectedGraphNode cur = stack.pop();12         for(int i=0;i<cur.neighbors.size();i++)13         {14             if(!map.containsKey(cur.neighbors.get(i)))15             {16                 copy = new UndirectedGraphNode(cur.neighbors.get(i).label);17                 map.put(cur.neighbors.get(i),copy);18                 stack.push(cur.neighbors.get(i));19             }20             map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));21         }22     }23     return map.get(node);24 }

用Recursion寫的DFS方法：

 1 public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { 2     if(node == null) 3         return null; 4     HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); 5     UndirectedGraphNode copy = new UndirectedGraphNode(node.label); 6     map.put(node,copy); 7     helper(node,map); 8     return copy; 9 }10 PRivate void helper(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map)11 {12     for(int i=0;i<node.neighbors.size();i++)13     { 14         UndirectedGraphNode cur = node.neighbors.get(i);15         if(!map.containsKey(cur))16         {17             UndirectedGraphNode copy = new UndirectedGraphNode(cur.label);18             map.put(cur,copy);19             helper(cur,map);20         }21         map.get(node).neighbors.add(map.get(cur));22     }23 }