复制无向图

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;
    }
}

直接
return node;
也可以通过...哈哈，这题还是要DFS或者BFS来写呀

思路：

1. 用深度优先DFS遍历，复制图
2. 用map保存新旧值的映射关系

    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;
    }
};

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) ; 
    }
}

/**  广搜，队列+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);
      }
  };