leetCode解题报告之Clone Graph
source link: https://blog.csdn.net/ljphhj/article/details/22292131
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题目：
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
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 node0to both nodes1and2. - Second node is labeled as
1. Connect node1to node2. - Third node is labeled as
2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
分析：
这个题目提供给我们一个已知的无向图，图上结点都有自己的值(label)还有和其他图结点的关系（包括和其他结点的连接关系，还有可能自己关联自己，形成环），要求我们要对这个已知图做一个“克隆”（有点类似于上次那题copy list的题目）
图上结点的数据结构：
class UndirectedGraphNode {
int label;
ArrayList<UndirectedGraphNode> neighbors;
UndirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<UndirectedGraphNode>();
解题思路：
首先，我们会想到，如果给你一个图上的结点，比如 结点0，它和结点 1 还有 结点 2 都有关联，如果我们要设置 结点0 的关联关系的List集合的话，如果结点 1 和结点 2已经存在的话，那么我们将不能再创建一遍已经存在的结点。
1. 我们会用一个HashMap<UndirectedGraphNode,UndirectedGraphNode> map， 来存储已经被我们new 出来的图上的结点
2. 为了能够把图上的所有结点都顺利的创建出来并且把它们的关联关系也确定好，我们需要有一个 队列， 先把 提供给我们的图上的一个结点放入 queue中，然后循环，取出队列中的“头结点”（tempNode），如果结点有和其他结点的关系List, 遍历关系结合List中的结点，如果结点不包括在map中，那么证明这个结点还没有被创建，此时我们copy一个该图结点，然后 map.put(OldNode, NewNode); 并把这个结点加入到新的结点的关系集合List中.
3. 为了避免“有环”（自己连接到自己的结点）的情况会一直重复，我们需要用一个 Set 集合来存下所有处理过的 图结点！
【讲得有点乱，具体看代码吧！】
AC代码：
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK