题目：
Clone an undirected graph. Each node in the graph contains a
labeland a list of itsneighbors
分析：
拷贝一个图。每个节点中用List存储它的邻居节点。
基本思路就是遍历原图，使用一个map来记录已经访问过的节点以及它和新节点的对应关系。
遍历可以考虑DFS或者BFS。下面的代码是使用BSF实现的。
代码：
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
/** * 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; Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>(); UndirectedGraphNode entrance = new UndirectedGraphNode(node.label); map.put(node, entrance); queue.add(node); while(!queue.isEmpty()){ UndirectedGraphNode oldNode = queue.poll(); UndirectedGraphNode newNode = map.get(oldNode); for(UndirectedGraphNode oldNeighbor : oldNode.neighbors){ if(!map.containsKey(oldNeighbor)){ map.put(oldNeighbor, new UndirectedGraphNode(oldNeighbor.label)); queue.add(oldNeighbor); } newNode.neighbors.add(map.get(oldNeighbor)); } } return entrance; } } |