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

---

节点是唯一的，就是要注意像例子中这样从2到2的环，有个test case是{0,0,0} DFS递归解法：

1 /** 2  * Definition for undirected graph. 3  * function UndirectedGraphNode(label) { 4  *     this.label = label; 5  *     this.neighbors = [];   // Array of UndirectedGraphNode 6  * } 7  */ 8 /** 9  * @param {UndirectedGraphNode} graph10  * @return {UndirectedGraphNode}11  */12 var cloneGraph = function(graph) {13     var visited = {};14     if(graph === null){15         return null;16     }else{17         return dfs(graph);18     }19 20     function dfs(node){21         var newNode = null;22         if(visited[node.label]){23             newNode = visited[node.label];24         }else{25             newNode = new UndirectedGraphNode(node.label);26             visited[node.label] = newNode;27         }28         for(var i = 0; i < node.neighbors.length; i++){29             if(node.neighbors[i].label !== node.label){30                 if(!visited[node.neighbors[i].label]){31                     newNode.neighbors.push(dfs(node.neighbors[i]));32                 }else{33                     newNode.neighbors.push(visited[node.neighbors[i].label]);34                 }35             }else{36                 newNode.neighbors.push(visited[node.label]);37             }38         }39         return newNode; 40     }   41 };

 

BFS非递归解法:

1 /** 2  * Definition for undirected graph. 3  * function UndirectedGraphNode(label) { 4  *     this.label = label; 5  *     this.neighbors = [];   // Array of UndirectedGraphNode 6  * } 7  */ 8  9 /**10  * @param {UndirectedGraphNode} graph11  * @return {UndirectedGraphNode}12  */13 var cloneGraph = function(graph) {14     var visited = {};15     var queue = [];16     if(graph === null){17         return null;18     }else{19         visited[graph.label] = new UndirectedGraphNode(graph.label);20         queue.push(graph);21         bfs();22         return visited[graph.label];23     }24 25     function bfs(){26         while(queue.length > 0){27             var node = queue.shift();28             var newNode = visited[node.label];29             for(var i = 0; i < node.neighbors.length; i++){30                 if(node.neighbors[i].label !== node.label){31                     var neighbor = node.neighbors[i];32                     var newNeighbor = null;33                     if(!visited[neighbor.label]){34                         newNeighbor = new UndirectedGraphNode(neighbor.label);35                         visited[neighbor.label] = newNeighbor;36                         queue.push(neighbor);37                     }else{38                         newNeighbor = visited[neighbor.label];39                     }40                     newNode.neighbors.push(newNeighbor);41                 }else{42                     newNode.neighbors.push(visited[node.label]);43                 }44             }45         }46     } 47 };