Clone Graph leetcode 자바 (DFS 및 BFS 기반)

제목:
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 hm = 
new HashMap();
 6         LinkedList queue = 
new LinkedList();
 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 hm = 
new HashMap();
 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 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 hm = 
new HashMap();
 6         LinkedList stack = 
new LinkedList();
 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     }