[Leetcode] Clone Graph 复制图

xietao3 发布于2019-08-14 12:29 / 2041人阅读

摘要：我们只要保证，对于第一次遇到的图节点，我们都会建立一个克隆节点，并在哈希表映射起来就行了。所以只要哈希表中有这个图节点，就说明我们之前已经将该图节点放入队列了，就不需要再处理了。

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ"s undirected graph serialization: Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle. Visually, the graph looks like the following:

   1
  / 
 /   
0 --- 2
     / 
     \_/

哈希表法 复杂度

时间 O(N) 空间 O(N)

思路

广度优先搜索，同时用一个哈希表，将新旧节点映射起来。这样我们第一次遍历到的节点，我们会新建一个节点并映射到哈希表中。当以后再遍历到这个节点时，我们可以直接用哈希表取出它对应的新节点。我们只要保证，对于第一次遇到的图节点，我们都会建立一个克隆节点，并在哈希表映射起来就行了。

注意

这里我们并不需要维护一个visited的集合，为什么呢？因为每次我们遇到一个之前没见过图节点，我们都会给它建立一个克隆节点，然后在哈希表中映射起来，并把这个图节点也放入队列中。所以只要哈希表中有这个图节点，就说明我们之前已经将该图节点放入队列了，就不需要再处理了。不过还是要把该图节点的克隆节点放入父克隆节点的邻居中。

代码

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) return null;
        Queue q = new LinkedList();
        Map map = new HashMap();
        UndirectedGraphNode root = new UndirectedGraphNode(node.label);
        map.put(node, root);
        q.offer(node);
        while(!q.isEmpty()){
            UndirectedGraphNode curr = q.poll();
            // 将curr旧节点的邻居节点都加入curr的新节点
            for(UndirectedGraphNode oldNeighbor : curr.neighbors){
                // 判断是否已经生成过该邻居节点的新节点
                if(!map.containsKey(oldNeighbor)){
                    // 如果是第一次生成该新节点，将其加入队列中
                    map.put(oldNeighbor, new UndirectedGraphNode(oldNeighbor.label));
                    q.offer(oldNeighbor);
                }
                // 将新邻居加入新curr节点的neighbors中
                map.get(curr).neighbors.add(map.get(oldNeighbor));
            }
        }
        return root;
    }
}

云服务器 GPU云服务器 graph LeetCode graph编程语言 LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64503.html

[LintCode/LeetCode] Clone Graph [BFS/DFS]

摘要：开始看这道题目的时候，没有看懂和的作用。然后对这个放入的结点开始操作遍历的所有，当前遍历到的的叫做。当完成，则中没有新的结点了，退出循环。返回在中更新过的，结束。 Problem Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. We use #...

fredshare 2019-08-14 15:23 评论0 收藏0
LeetCode 133：克隆图 Clone Graph

摘要：解题思路涉及到图的遍历无非就是深度优先搜索广度优先搜索，可以先看前几日的这篇文章就需要借助队列实现，可以借助栈也可以直接用递归实现。题目：给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int）和其邻居的列表（list[Node]）。 Given a reference of a node in a connected undirec...

Simon 2019-08-19 10:35 评论0 收藏0
【算法】剑指 Offer II 110. 所有路径｜797. 所有可能的路径（多语言实现）

摘要：遍历路径，找到所有可以到达终点节点的路径就是结果。提示中说保证输入为有向无环图，所以我们可以认为节点间一定有着某种排列的顺序，从头到尾怎样可以有最多的路径呢，那就是在保证没有环路的情况下，所有节点都尽可能多的连接着其他节点。 ...

wangdai 2021-11-23 09:51 评论0 收藏0
[Leetcode] Alien Dictionary 外文字典

摘要：拓扑排序复杂度时间空间思路首先简单介绍一下拓扑排序，这是一个能够找出有向无环图顺序的一个方法假设我们有条边，先将每个节点的计数器初始化为。最后，我们开始拓扑排序，从计数器为的字母开始广度优先搜索。 Alien Dictionary There is a new alien language which uses the latin alphabet. However, the ord...

pkhope 2019-08-14 12:38 评论0 收藏0
[Leetcode] Course Schedule 课程计划

Course Schedule I There are a total of n courses you have to take, labeled from 0 to n - 1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is e...

Amio 2019-08-14 12:40 评论0 收藏0