133.Clone Graph (M)
https://leetcode.com/problems/clone-graph/
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}
Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Example 1:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).Example 2:
Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.Example 3:
Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
Constraints:
The number of nodes in the graph is in the range
[0, 100].1 <= Node.val <= 100Node.valis unique for each node.There are no repeated edges and no self-loops in the graph.
The Graph is connected and all nodes can be visited starting from the given node.
Solution
深度拷贝
表怎么存储：1.邻接表
Class Graph{
int node;
ArrayList<Node> neighbor;
}
2.邻接矩阵（矩阵里存点）
Version 1:BFS ：时间复杂度O(n)，空间复杂度O(n)
从原图给定的点找到所有点
复制所有的点
复制所有的边
HashMap里存放的是原节点和复制节点的对应关系，防止建立重复的新节点。
queue里存放原图节点的BFS遍历。
先复制一个头结点，将他们的map存进HashMap.然后头节点进入队列
每一次queue出列一个node,然后检查这个node对的所有neighbor,如果没有被visited,就产生一个新的复制节点并把们的关系放进map
然后建立这个复制关系的neighbor链表，将每一个neighbor的复制节点都放进当前复制节点的neighbor list.
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node==null){
return null;
}
UndirectedGraphNode copynode=new UndirectedGraphNode(node.label);
HashMap<UndirectedGraphNode,UndirectedGraphNode> map=new HashMap<>();
Queue<UndirectedGraphNode> queue=new LinkedList<UndirectedGraphNode>();
//新旧节点的对应
map.put(node, copynode);
queue.offer(node);
while(!queue.isEmpty()){
UndirectedGraphNode current=queue.poll();
//copy node
for(UndirectedGraphNode neighbor:current.neighbors){
if(!map.containsKey(neighbor)){
queue.offer(neighbor);
UndirectedGraphNode copyneighbor=new UndirectedGraphNode(neighbor.label);
map.put(neighbor,copyneighbor);
}
//connect
//这段应该放在外面，避免当前节点连接的是已经复制过的点。
UndirectedGraphNode copy=map.get(current);
copy.neighbors.add(map.get(neighbor));
}
}
return copynode;
}与上面同一解法，在处理visited反过来
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node==null){
return null;
}
UndirectedGraphNode copynode=new UndirectedGraphNode(node.label);
HashMap<UndirectedGraphNode,UndirectedGraphNode> map=new HashMap<>();
Queue<UndirectedGraphNode> queue=new LinkedList<UndirectedGraphNode>();
//新旧节点的对应
map.put(node, copynode);
queue.offer(node);
while(!queue.isEmpty()){
UndirectedGraphNode current=queue.poll();
for(UndirectedGraphNode neighbor:current.neighbors){
if(map.containsKey(neighbor)){
//如果已经存在，直接把他的neighbor复制过去
UndirectedGraphNode copy=map.get(current);
copy.neighbors.add(map.get(neighbor));
}
else{
queue.offer(neighbor);
UndirectedGraphNode copyneighbor=new UndirectedGraphNode(neighbor.label);
map.put(neighbor,copyneighbor);
map.get(current).neighbors.add(copyneighbor);
}
}
}
return copynode;
}//*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
private Map<Node, Node> map;
public Node cloneGraph(Node node) {
if (node == null) {
return node;
}
map = new HashMap<>();
Set<Node> originalNodeSet = getNodes(node);
// copy Edges
for(Node original : originalNodeSet)
{
for(Node originalNeighbor : original.neighbors)
{
map.get(original).neighbors.add(map.get(originalNeighbor));
}
}
return map.get(node);
}
// Copy Node
public Set<Node> getNodes(Node node)
{
Set<Node> res = new HashSet<>();
Queue<Node> queue = new LinkedList<Node>();
map.put(node, new Node(node.val));
queue.offer(node);
while(!queue.isEmpty())
{
Node current = queue.poll();
res.add(current);
for(Node adj: current.neighbors)
{
if(!res.contains(adj))
{
map.put(adj, new Node(adj.val));
queue.offer(adj);
}
}
}
return res;
}
}九章answer : http://www.jiuzhang.com/solutions/clone-graph/
http://www.cnblogs.com/springfor/p/3874591.html
Version 2：DFS(Time exceed)
public UndirectedGraphNode cloneGraph2(UndirectedGraphNode node){
if(node==null){
return null;
}
HashMap<UndirectedGraphNode, UndirectedGraphNode> hm=new HashMap<>();
UndirectedGraphNode head=new UndirectedGraphNode(node.label);
hm.put(node, head);
dfs(hm,node);
return head;
}
public void dfs(HashMap<UndirectedGraphNode, UndirectedGraphNode> hm, UndirectedGraphNode node){
if(node==null){
return;
}
for(UndirectedGraphNode aneighbor: node.neighbors){
if(!hm.containsKey(aneighbor)){
UndirectedGraphNode copynode=new UndirectedGraphNode(aneighbor.label);
hm.put(aneighbor, copynode);
hm.get(node).neighbors.add(copynode);
}else{
dfs(hm,aneighbor);
}
}
}Last updated
Was this helpful?