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 node0
to both nodes1
and2
. - Second node is labeled as
1
.
Connect node1
to node2
. - Third node is labeled as
2
.
Connect node2
to node2
(itself),
thus forming a self-cycle.
Visually, the graph looks like the following:
1 / \ / \ 0 --- 2 / \ \_/
解题思路:
1. 用一个Queue来存储待处理的节点
2. 遍历的时候对于不存在的节点先要创建出来,所有节点通过Map<int,node> 的方式实现快速存取
/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * ArrayList<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { /** * @param node: A undirected graph node * @return: A undirected graph node */ public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if(node == null) return null; Map<Integer,UndirectedGraphNode> map = new HashMap<Integer,UndirectedGraphNode>(); Set<Integer> pass = new HashSet<Integer>(); Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); queue.offer(node); pass.add(node.label); map.put(node.label,new UndirectedGraphNode(node.label)); UndirectedGraphNode t = null; while((t = queue.poll()) !=null){ UndirectedGraphNode t1 = map.get(t.label); ArrayList<UndirectedGraphNode> neighbors = new ArrayList<UndirectedGraphNode>(); for(UndirectedGraphNode n : t.neighbors){ if(map.get(n.label)==null){ map.put(n.label,new UndirectedGraphNode(n.label)); queue.offer(n); } neighbors.add(map.get(n.label)); } t1.neighbors = neighbors; } return map.get(node.label); } }