力扣（LeetCode）-133 克隆图

本地考察的是图搜索

题目描述

克隆一张无向图，图中的每个节点包含一个 label （标签）和一个 neighbors （邻接点）列表 。
OJ的无向图序列化：
节点被唯一标记。
我们用 # 作为每个节点的分隔符，用 , 作为节点标签和邻接点的分隔符。
例如，序列化无向图 {0,1,2#1,2#2,2}。
该图总共有三个节点, 被两个分隔符 # 分为三部分。
第一个节点的标签为 0，存在从节点 0 到节点 1 和节点 2 的两条边。
第二个节点的标签为 1，存在从节点 1 到节点 2 的一条边。
第三个节点的标签为 2，存在从节点 2 到节点 2 (本身) 的一条边，从而形成自环。
我们将图形可视化如下：

image.png

题目思考

首先应该对图进行遍历，使用深度优先搜索或者广度优先搜索都可以，在遍历的过程中不断克隆结点。使用HashMap来保存已克隆的结点。

代码

使用队列

public class Solution {
    //BFS
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node==null)
            return null;
        Map<Integer,UndirectedGraphNode> map=new HashMap<Integer,UndirectedGraphNode>();//保存已克隆的结点
        Queue<UndirectedGraphNode> queue1=new LinkedList<UndirectedGraphNode>();//使用队列继续宁深度优先搜索
        queue1.offer(node);
        UndirectedGraphNode head=new UndirectedGraphNode(node.label);
        map.put(head.label,head);
        while(!queue1.isEmpty()){
            UndirectedGraphNode temp =queue1.poll();
            List<UndirectedGraphNode> temp_list = temp.neighbors;
            for(int i=0;i<temp_list.size();i++){//为该节点添加相邻结点
                UndirectedGraphNode temp_neighbor =temp_list.get(i);
                UndirectedGraphNode new_node=map.get(temp_neighbor.label);
                if(new_node==null){//如果还没有创建该相邻结点，创建并添加到map中
                    new_node=new UndirectedGraphNode(temp_neighbor.label);
                    map.put(temp_neighbor.label,new_node);
                    queue1.offer(temp_neighbor);
                }
                map.get(temp.label).neighbors.add(new_node);
            }
        }
        return head;
    }
}

使用递归