package go.jacob.day815;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
* 133. Clone Graph
* @author Jacob
* 牛客的测试不够严谨，直接返回node也是可以通过的
*
* 以下分享DFS循环和递归实现
*/
public class Demo1 {
/*
* 循环实现
*/
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null)
return null;
// map存储旧节点到新节点的映射
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
UndirectedGraphNode head = new UndirectedGraphNode(node.label);
map.put(node, head);
// DFS需要用到栈
Stack<UndirectedGraphNode> stack = new Stack<UndirectedGraphNode>();
stack.push(node);
while (!stack.isEmpty()) {
UndirectedGraphNode root = stack.pop();
ArrayList<UndirectedGraphNode> lists = new ArrayList<UndirectedGraphNode>();
for (UndirectedGraphNode n : root.neighbors) {
if (map.containsKey(n)) {
lists.add(map.get(n));
} else {
UndirectedGraphNode n1 = new UndirectedGraphNode(n.label);
stack.push(n);
map.put(n, n1);
lists.add(n1);
}
}
System.out.println(map.containsKey(root));
map.get(root).neighbors = lists;
}
return head;
}
/*
* 递归实现
*/
private HashMap<Integer, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph_1(UndirectedGraphNode node) {
return clone(node);
}
private UndirectedGraphNode clone(UndirectedGraphNode node) {
if (node == null) return null;
if (map.containsKey(node.label)) {
return map.get(node.label);
}
UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
map.put(clone.label, clone);
for (UndirectedGraphNode neighbor : node.neighbors) {
clone.neighbors.add(clone(neighbor));
}
return clone;
}
}
/**
* 题目解析：给定一个无向图，图内节点包括节点值、节点的邻居；需要复制该图
* 解题思路：
* 图的遍历可添加一个辅助队列来左广度优先搜索
* 再者，因为节点未给是否已经访问的属性，可以添加一个map来记录已经访问的节点，和复制的节点
* 同时map帮助复制 邻居节点
*/
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
// 建立辅助队列
LinkedList<UndirectedGraphNode> queue = new LinkedList<>();
// 建立map，跟踪已经访问的节点
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
// 节点入队
queue.offer(node);
// 复制节点-只复制了label域，neighbors域是引用对象，直接复制无意义
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
// 节点进入代表已经访问的map
map.put(node, newNode);
// 中断条件：队列为空
while(!queue.isEmpty()) {
// 出队
UndirectedGraphNode temp = queue.poll();
// 获取邻居，遍历邻居
ArrayList<UndirectedGraphNode> neighbors = temp.neighbors;
for(UndirectedGraphNode neighbor : neighbors) {
// 声明当前邻居节点 的 复制节点
UndirectedGraphNode copy;
// 若邻居未访问过
if (!map.containsKey(neighbor)) {
// 该邻居节点入队
queue.offer(neighbor);
// 复制该邻居节点
copy = new UndirectedGraphNode(neighbor.label);
// 将未访问邻居记录进map
map.put(neighbor, copy);
} else {
// 邻居节点 之前被访问过
// 获取邻居节点的复制节点
copy = map.get(neighbor);
}
// 无论当前邻居节点 是否被访问过
// 它的复制节点 都应该跟 复制的根节点建立 邻居关系
map.get(temp).neighbors.add(copy);
}
}
// 返回 复制的图
return newNode;
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
/**
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
DFS 和 BFS 遍历
1)克隆结点 label;
2)克隆结点与临近结点关系
深度遍历或者广度优先遍历复制 label，同时用 map 记录复制的node 和对应的 neighbors
*/
public class Solution {
/**
class UndirectedGraphNode {
int label;
ArrayList<UndirectedGraphNode> neighbors;
UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<>(); }
};
*/
/**
* 递归的方式实现 DFS
*/
public UndirectedGraphNode cloneGraph1(UndirectedGraphNode node) {
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
return dfs(node, map);
}
/**
* 递归方式实现深度优先遍历
*/
private UndirectedGraphNode dfs(UndirectedGraphNode root,
Map<UndirectedGraphNode, UndirectedGraphNode> map) {
if (root == null)
return null;
// 复制root节点
UndirectedGraphNode cloneRoot = new UndirectedGraphNode(root.label);
map.put(root, cloneRoot);
// 遍历 root 的邻居节点
for (UndirectedGraphNode neighbor : root.neighbors) {
if (map.containsKey(neighbor)) {
// 取出来直接添加到新复制的节点的neighbors
cloneRoot.neighbors.add(map.get(neighbor));
} else {
UndirectedGraphNode neighborClone = dfs(neighbor, map);
cloneRoot.neighbors.add(neighborClone);
}
}
return cloneRoot;
}
/**
* 利用队列实现非递归的 BFS
*/
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null)
return null;
// 未访问结点的队列
LinkedList<UndirectedGraphNode> queue = new LinkedList<>();
queue.push(node);
// 原始节点和已复制节点的映射
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
UndirectedGraphNode cloneRoot = new UndirectedGraphNode(node.label);
map.put(node, cloneRoot);
while (!queue.isEmpty()) {
UndirectedGraphNode snode = queue.pop();
UndirectedGraphNode snodeClone = map.get(snode);
// 遍历复制 snode 的邻居节点
for (UndirectedGraphNode neighbor : snode.neighbors) {
// 如果 neighbor 已经复制，直接取出进行添加
if (map.containsKey(neighbor)) {
snodeClone.neighbors.add(map.get(neighbor));
} else {
// 复制新的邻居节点
UndirectedGraphNode cloneNeighbor = new UndirectedGraphNode(neighbor.label);
map.put(neighbor, cloneNeighbor);
snodeClone.neighbors.add(cloneNeighbor);
queue.push(neighbor);
}
}
}
return cloneRoot;
}
}
思路：
std::map<UndirectedGraphNode *,UndirectedGraphNode *> m;
std::map<UndirectedGraphNode *,UndirectedGraphNode *>::iterator iter;
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node) return node;
return cloneGraphHelp(node);
}
UndirectedGraphNode *cloneGraphHelp(UndirectedGraphNode *node){
iter = m.end();
iter = m.find(node);
if(iter != m.end()) return iter->second;//已经创建的结点直接在map中查找
UndirectedGraphNode *p;
p = new UndirectedGraphNode(node->label);
m.insert(std::pair<UndirectedGraphNode *,UndirectedGraphNode *>(node,p));
for(int i = 0;i < node->neighbors.size();i++)
p->neighbors.push_back(cloneGraphHelp(node->neighbors[i]));
return p;
}
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(!node) return NULL;
unordered_map<UndirectedGraphNode *,UndirectedGraphNode *> mp;
UndirectedGraphNode *p=new UndirectedGraphNode(node->label);
mp[node]=p;
queue<UndirectedGraphNode *> q;
q.push(node);
while(q.size()){
UndirectedGraphNode *u=q.front();q.pop();
for(auto v:u->neighbors) {
if(!mp[v]){
UndirectedGraphNode *next=new UndirectedGraphNode(v->label);
mp[v]=next;
q.push(v);
}
mp[u]->neighbors.push_back(mp[v]);
}
}
return p;
}
}; 
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
void dfs(UndirectedGraphNode* node) {
if (node == nullptr) { return; }
if (mp.count(node)) { return; }
UndirectedGraphNode *copyNode = new UndirectedGraphNode(node->label);
mp[node] = copyNode;
for (auto n : node->neighbors) {
dfs(n);
}
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
UndirectedGraphNode* oldNode = node;
dfs(node);
for (auto n : mp) {
UndirectedGraphNode *first = n.first;
for (int i = 0; i < first->neighbors.size(); i++) {
n.second->neighbors.push_back(mp[first->neighbors[i]]);
}
}
return mp[oldNode];
} 
import java.util.* ;
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode dfs(UndirectedGraphNode root , Map<UndirectedGraphNode,UndirectedGraphNode> map){
if(root == null){
return null;
}
UndirectedGraphNode clone = new UndirectedGraphNode(root.label) ;
map.put(root ,clone) ;
for(UndirectedGraphNode node: root.neighbors){
if(map.containsKey(node)){
clone.neighbors.add(map.get(node)) ;
}else{
UndirectedGraphNode next = dfs(node , map) ;
clone.neighbors.add(next) ;
}
}
return clone;
}
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
Map<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<>() ;
return dfs(node , map) ;
}
}
import java.util.*;
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return node;
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
map.put(node, new UndirectedGraphNode(node.label));
Queue<UndirectedGraphNode> queue = new LinkedList<>();
queue.offer(node);
while(!queue.isEmpty()){
UndirectedGraphNode cur = queue.poll();
for(UndirectedGraphNode neighbor: cur.neighbors){
if(!map.containsKey(neighbor)){
map.put(neighbor, new UndirectedGraphNode(neighbor.label));
queue.offer(neighbor);
}
map.get(cur).neighbors.add(map.get(neighbor));
}
}
return map.get(node);
}
} 
/** 广搜，队列+map，map解决环问题
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
Queue<UndirectedGraphNode> queue = new LinkedList();
HashMap<Integer, UndirectedGraphNode> map = new HashMap();
UndirectedGraphNode res = new UndirectedGraphNode(node.label);
map.put(res.label, res);
queue.offer(node);
while (!queue.isEmpty()){
UndirectedGraphNode tmp = queue.poll();
UndirectedGraphNode newNode = map.get(tmp.label);
for (UndirectedGraphNode neighbor : tmp.neighbors){
if (!map.containsKey(neighbor.label)){
map.put(neighbor.label, new UndirectedGraphNode(neighbor.label));
queue.offer(neighbor);
}
newNode.neighbors.add(map.get(neighbor.label));
}
}
return res;
}
}
import java.util.HashMap;
public class Solution {
HashMap map;
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
UndirectedGraphNode newGraph=null;
if(node==null)return newGraph;
map=new HashMap<Integer,UndirectedGraphNode>();
newGraph=new UndirectedGraphNode(node.label);
map.put(node.label,newGraph);
lookUp(newGraph,node);
return newGraph;
}
public void lookUp(UndirectedGraphNode newnode,UndirectedGraphNode rootNode){
for(UndirectedGraphNode node:rootNode.neighbors){
if(map.containsKey(node.label)){
UndirectedGraphNode newGraph=(UndirectedGraphNode)map.get(node.label);
newnode.neighbors.add(newGraph);
continue;
}
UndirectedGraphNode newGraph=new UndirectedGraphNode(node.label);
map.put(node.label,newGraph);
newnode.neighbors.add(newGraph);
lookUp(newGraph,node);
}
}
}
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* ArrayList<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
import java.util.LinkedList;//队列
import java.util.HashMap;
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
/*
克隆无向图(1)克隆结点label;2)克隆结点与临近结点关系)
HashMap+BFS
HashMap用于保存label与克隆结点的对应关系，用于找到对应值为label的克隆结点(结点与克隆结点的联系在于label)
BFS用一个队列来维护未访问结点，通过广度有限搜索策略，不断克隆遍历到的结点并更新结点间的邻近关系
*/
if (node==null){
return null;
}
LinkedList<UndirectedGraphNode> queue=new LinkedList<UndirectedGraphNode>();
queue.add(node);//未访问结点入队
HashMap<Integer,UndirectedGraphNode> map=new HashMap<Integer,UndirectedGraphNode>();
UndirectedGraphNode clonenode= new UndirectedGraphNode(node.label);//克隆结点
map.put(clonenode.label,clonenode);//保存克隆结点label与克隆结点的对应关系
while (!queue.isEmpty()){//队不为空，即还有未遍历结点
UndirectedGraphNode snode=queue.remove();//出队，即访问队首结点
UndirectedGraphNode sclonenode=map.get(snode.label);//通过结点label找到克隆结点
for(int i=0;i<snode.neighbors.size();i++){//克隆该结点的邻近结点及其与邻近结点的关系
UndirectedGraphNode nnode=snode.neighbors.get(i);//取第i个邻近结点克隆
if (map.get(nnode.label)==null){//邻近结点未克隆
UndirectedGraphNode clone_nnode= new UndirectedGraphNode(nnode.label);//克隆邻近结点
map.put(clone_nnode.label,clone_nnode);//保存克隆结点label与克隆结点的对应关系
queue.add(nnode);//未访问结点入队(非克隆的结点)
}
UndirectedGraphNode sclone_nnode=map.get(nnode.label);//邻近结点
sclonenode.neighbors.add(sclone_nnode);//保存邻近关系
}
}
return clonenode;
}
}
class Solution {
public:
map<int,UndirectedGraphNode*> record;
UndirectedGraphNode *clone(UndirectedGraphNode *node) {
UndirectedGraphNode *ngraph,*p;
map<int,UndirectedGraphNode*>::iterator iter;
p=node;
iter=record.find(p->label);
if(iter!=record.end())
return iter->second;
ngraph=new UndirectedGraphNode(p->label);
record.insert(map<int,UndirectedGraphNode*>::value_type(p->label,ngraph));
for(int i=0;i<p->neighbors.size();i++){
ngraph->neighbors.push_back(clone(p->neighbors[i]));
}
return ngraph;
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node){
UndirectedGraphNode *ngraph;
if(node==NULL)
return NULL;
record.clear();
ngraph=clone(node);
return ngraph;
}
};
首先，这是个图的问题，二话不说，咱先搬出BFS和DFS两大法宝。
基本思路是：创建一个unordered_map，其中保存指向旧节点的指针到指向新节点的指针的映射，同时也用它来判断旧节点是否被遍历过。
BFS代码如下：
//
// Created by jt on 2020/9/23.
//
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (!node) return nullptr;
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
queue<UndirectedGraphNode*> qu;
qu.push(node);
// BFS
while (!qu.empty()) {
UndirectedGraphNode* oldNode = qu.front();
qu.pop();
UndirectedGraphNode* newNode = mp.count(oldNode) != 0
? mp[oldNode] : new UndirectedGraphNode(oldNode->label);
mp[oldNode] = newNode;
for (auto p : oldNode->neighbors) {
UndirectedGraphNode* q;
if (mp.count(p) != 0) {
q = mp[p];
} else {
q = new UndirectedGraphNode(p->label);
mp[p] = q;
// 如果旧节点没有遍历过，加入队列
qu.push(p);
}
newNode->neighbors.push_back(q);
}
}
return mp[node];
}
};DFS代码如下：
//
// Created by jt on 2020/9/23.
//
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (!node) return nullptr;
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
return dfs(node, mp);
}
UndirectedGraphNode* dfs(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> &mp) {
if (!node) return nullptr;
if (mp.count(node) != 0) return mp[node];
UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
mp[node] = newNode;
for (auto p : node->neighbors) {
newNode->neighbors.push_back(dfs(p, mp));
}
return newNode;
}
};
class Solution{
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(node == NULL) return NULL;
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*>mmp;
queue<UndirectedGraphNode*> qq;
qq.push(node);
UndirectedGraphNode *res = new UndirectedGraphNode(node->val);
mmp[node] = res;
while (!qq.empty()){
UndirectedGraphNode *neighbor_temp = qq.front(); qq.pop();
for (UndirectedGraphNode* unit : neighbor_temp->neighbors){
if (mmp.count(unit) == 0){
//not found
mmp[unit] = new UndirectedGraphNode(unit->val);
qq.push(unit);
}
mmp[neighbor_temp]->neighbors.push_back(mmp[unit]);
}
}//end for while
return res;
}
};
class Solution{
public:
Node* copyRandomList(Node *root){
if (root == NULL) return NULL;
unordered_map<Node*, Node*>mmp;
Node *res = root;
mmp[root] = new Node(root->val);
//connect
while (root != NULL){
if (root->next == NULL){
mmp[root]->next = NULL;
}else{
if (mmp.count(root->next) == 0){
mmp[root->next] = new Node(root->next->val);
}
mmp[root]->next = mmp[root->next];
}
if (root->random == NULL){
mmp[root]->random = NULL;
}else{
if (mmp.count(root->random) == 0){
mmp[root->random] = new Node(root->random->val);
}
mmp[root]->random = mmp[root->random];
}
root = root->next;
}
return mmp[res];
}
}; 
// 深度优先遍历，用map记录访问过的节点，以及新创建的节点
class Solution {
public:
map<UndirectedGraphNode*,int> m;
map<UndirectedGraphNode*,UndirectedGraphNode*> on;
UndirectedGraphNode* dfs(UndirectedGraphNode* node){
if(node==nullptr)
return nullptr;
if(node->neighbors.size()==0)
return new UndirectedGraphNode(node->label);
auto ret=new UndirectedGraphNode(node->label);
m[node]=1;
on[node]=ret;
for(auto c:node->neighbors){
if(m[c]==0)
ret->neighbors.push_back(dfs(c));
else
ret->neighbors.push_back(on[c]);
}
return ret;
}
UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node) {
return dfs(node);
}
};
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
