137. Clone Graph
2019-05-30 本文已影响0人
鸭蛋蛋_8441
Description
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. Nodes are labeled uniquely.
You need to return a deep copied graph, which has the same structure as the original graph, and any changes to the new graph will not have any effect on the original graph.
You need return the node with the same label as the input node.
Clarification
How we serialize an undirected graph: http://www.lintcode.com/help/graph/
Example
Example1
Input:
{1,2,4#2,1,4#4,1,2}
Output:
{1,2,4#2,1,4#4,1,2}
Explanation:
1------2
\ |
\ |
\ |
\ |
4
思路：
（并看不懂，等后续补充）使用宽度优先搜索 BFS 的版本。
第一步：找到所有的点
第二步：复制所有的点，将映射关系存起来
第三步：找到所有的边，复制每一条边
代码：
