# leetcode 133. Clone Graph

xiaoxiao2021-03-25  38

今天换换口味，来一题数据结构题

对于一个图，如何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)); } } } }