Clone Graph leetcode java（DFS and BFS 基础）

浏览数：36 / 时间：2015年06月08日

题目：

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

题解：
这道题考察对图的遍历和利用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 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.”

通常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     }

Clone Graph leetcode java（DFS and BFS 基础）,古老的榕树,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Clone Graph leetcode java（DFS and BFS 基础）