今天换换口味，来一题数据结构题
对于一个图，如何clone它呢
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 / \ \_/
Subscribe to see which companies asked this question.
题目如上，可以建一个哈希表，将新老节点一一对应，然后再复制其邻居节点链表即可/** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if(node==null)return null; help(node); for(Map.Entry<UndirectedGraphNode,UndirectedGraphNode>entry:map.entrySet()){ List<UndirectedGraphNode> list=entry.getKey().neighbors; List<UndirectedGraphNode> newlist=new ArrayList<UndirectedGraphNode>(); for(int i=0;i<list.size();i++){ newlist.add(map.get(list.get(i))); } entry.getValue().neighbors=newlist; } return newheadall; } UndirectedGraphNode newheadall; HashMap<UndirectedGraphNode,UndirectedGraphNode> map=new HashMap<>(); boolean mark=true; public void help(UndirectedGraphNode node){ UndirectedGraphNode newnode=new UndirectedGraphNode(node.label); map.put(node,newnode); if(mark){ mark=false; newheadall=newnode; } List<UndirectedGraphNode> list=node.neighbors; for(int i=0;i<list.size();i++){ if(!map.containsKey(list.get(i))){ help(list.get(i)); } } } }
