題目：

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/ \\_/


題解：
引用：http://www.cnblogs.com/springfor/p/3874591.html
這道題考察對圖的遍歷和利用HashMap拷貝的方法。
對圖的遍歷就是兩個經典的方法DFS和BFS。BFS經常用Queue實現，DFS經常用遞歸實現（可改為棧實現）。
拷貝方法是用用HashMap，key存原始值，value存copy的值，用DFS,BFS方法遍歷幫助拷貝neighbors的值。

先復習下DFS和BFS。

DFS（Dpeth-first Search）
顧名思義，就是深度搜索，一條路走到黑，再選新的路。
記得上Algorithm的時候，教授舉得例子就是說，DFS很像好奇的小孩，你給這個小孩幾個盒子套盒子，好奇的小孩肯定會一個盒子打開后繼續再在這個盒子里面搜索。
等把這一套盒子都打開完，再打開第二套的。
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寫法是用遞歸，如果非遞歸的話就是棧套迭代，思想是一樣的。
遞歸寫法的DFS偽代碼如下：
Input: A graph G and a root v of G 1???procedure?DFS(G,v):
2???????label?v?as?discovered
3???????for?all?edges?from?v?to?w?in?G.adjacentEdges(v)?do
4???????????if?vertex?w?is?not?labeled?as?discovered?then
5???????????????recursively?call?DFS(G,w) 非遞歸寫法的DFS偽代碼如下：
Input: A graph G and a root v of G 1???procedure?DFS-iterative(G,v):
2???????let?S?be?a?stack
3???????S.push(v)
4???????while?S?is?not?empty
5?????????????v?←?S.pop()?
6?????????????if?v?is?not?labeled?as?discovered:
7?????????????????label?v?as?discovered
8?????????????????for?all?edges?from?v?to?w?in?G.adjacentEdges(v)?do
9?????????????????????S.push(w)


BFS（Breadth-first Search）
這個就是相對于BFS的另外一種對圖的遍歷方法，對于一個節點來說先把所有neighbors都檢查一遍，再從第一個neighbor開始，循環往復。
由于BFS的這個特質，BFS可以幫助尋找最短路徑。
Wikipedia上面對BFS的定義是：
“In graph theory, breadth-first search (BFS) is a strategy for searching in a graphwhen 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.”

通常BFS用queue+循環實現，偽代碼如下：
Input: A graph G and a root v of G 1???procedure?BFS(G,v)?is
?2???????create?a?queue?Q
?3???????create?a?set?V
?4???????add?v?to?V
?5???????enqueue?v?onto?Q
?6???????while?Q?is?not?empty?loop
?7??????????t?←?Q.dequeue()
?8??????????if?t?is?what?we?are?looking?for?then
?9?????????????return?t
10?????????end?if
11?????????for?all?edges?e?in?G.adjacentEdges(t)?loop
12????????????u?←?G.adjacentVertex(t,e)
13????????????if?u?is?not?in?V?then
14????????????????add?u?to?V
15????????????????enqueue?u?onto?Q
16????????????end?if
17?????????end?loop
18??????end?loop
19??????return?none
20??end?BFS ********************************************************************************************************************************
下面就是這道題的3種解題方法。

第一種實現方法是BFS的，就是先將頭節點入queue，每一次queue出列一個node，然后檢查這個node的所有的neighbors，如果沒visited過，就入隊，并更新neighbor。
然后更新新的neighbor列表。
代碼如下： 1?????public?UndirectedGraphNode?cloneGraph(UndirectedGraphNode?node)?{
?2?????????if(node?==?null)
?3?????????????return?null;
?4?????????????
?5?????????HashMap<UndirectedGraphNode,?UndirectedGraphNode>?hm?=?new?HashMap<UndirectedGraphNode,?UndirectedGraphNode>();
?6?????????LinkedList<UndirectedGraphNode>?queue?=?new?LinkedList<UndirectedGraphNode>();
?7?????????UndirectedGraphNode?head?=?new?UndirectedGraphNode(node.label);
?8?????????hm.put(node,?head);
?9?????????queue.add(node);
10?????????
11?????????while(!queue.isEmpty()){
12?????????????UndirectedGraphNode?curnode?=?queue.poll();
13?????????????for(UndirectedGraphNode?aneighbor:?curnode.neighbors){//check?each?neighbor
14?????????????????if(!hm.containsKey(aneighbor)){//if?not?visited,then?add?to?queue
15?????????????????????queue.add(aneighbor);
16?????????????????????UndirectedGraphNode?newneighbor?=?new?UndirectedGraphNode(aneighbor.label);
17?????????????????????hm.put(aneighbor,?newneighbor);
18?????????????????}
19?????????????????
20?????????????????hm.get(curnode).neighbors.add(hm.get(aneighbor));
21?????????????}
22?????????}
23?????????
24?????????return?head;
25?????} DFS的遞歸操作如下，迭代復制neighbors： 1?????public?UndirectedGraphNode?cloneGraph(UndirectedGraphNode?node)?{
?2?????????if(node?==?null)
?3?????????????return?null;
?4?????????????
?5?????????HashMap<UndirectedGraphNode,?UndirectedGraphNode>?hm?=?new?HashMap<UndirectedGraphNode,?UndirectedGraphNode>();
?6?????????UndirectedGraphNode?head?=?new?UndirectedGraphNode(node.label);
?7?????????hm.put(node,?head);
?8?????????
?9?????????DFS(hm,?node);//DFS
10?????????return?head;
11?????}
12?????public?void?DFS(HashMap<UndirectedGraphNode,?UndirectedGraphNode>?hm,?UndirectedGraphNode?node){
13?????????if(node?==?null)
14?????????????return;
15?????????????
16?????????for(UndirectedGraphNode?aneighbor:?node.neighbors){?
17?????????????if(!hm.containsKey(aneighbor)){
18?????????????????UndirectedGraphNode?newneighbor?=?new?UndirectedGraphNode(aneighbor.label);
19?????????????????hm.put(aneighbor,?newneighbor);
20?????????????????DFS(hm,?aneighbor);//DFS
21?????????????}
22?????????????hm.get(node).neighbors.add(hm.get(aneighbor));
23?????????}
24?????}

下面一種方法是DFS的非遞歸方法，中點是把BFS中的queue換成stack，因為出列方法不一樣了，所以遍歷的線路就不一樣了。代碼如下: 1?????public?UndirectedGraphNode?cloneGraph(UndirectedGraphNode?node)?{
?2?????????if(node?==?null)
?3?????????????return?null;
?4?????????????
?5?????????HashMap<UndirectedGraphNode,?UndirectedGraphNode>?hm?=?new?HashMap<UndirectedGraphNode,?UndirectedGraphNode>();
?6?????????LinkedList<UndirectedGraphNode>?stack?=?new?LinkedList<UndirectedGraphNode>();
?7?????????UndirectedGraphNode?head?=?new?UndirectedGraphNode(node.label);
?8?????????hm.put(node,?head);
?9?????????stack.push(node);
10?????????
11?????????while(!stack.isEmpty()){
12?????????????UndirectedGraphNode?curnode?=?stack.pop();
13?????????????for(UndirectedGraphNode?aneighbor:?curnode.neighbors){//check?each?neighbor
14?????????????????if(!hm.containsKey(aneighbor)){//if?not?visited,then push to stack
15?????????????????????stack.push(aneighbor);
16?????????????????????UndirectedGraphNode?newneighbor?=?new?UndirectedGraphNode(aneighbor.label);
17?????????????????????hm.put(aneighbor,?newneighbor);
18?????????????????}
19?????????????????
20?????????????????hm.get(curnode).neighbors.add(hm.get(aneighbor));
21?????????????}
22?????????}
23?????????
24?????????return?head;
25?????}

?

轉載于:https://www.cnblogs.com/fengmangZoo/p/4192777.html

總結

以上是生活随笔為你收集整理的[leetcod] Clone Graph的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。