LeetCode 133:克隆图(图的深度优先遍历DFS和广度优先遍历BFS)

回顾

图的Node数据结构

图的数据结构,以下两种都可以,dfs和bfs的板子是不变的。

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

```java
public class Node{
    public int value;//点的编号,不一定是Integer类型的,要看具体的题,有的题点编号为字母。
    public int in;//入度
    public int out;//出度
    public ArrayList<Node>nexts;//出去的边直接相连的邻居。
    public ArrayList<Edge>edges//出去的边

    public Node(int value){
        this.value=value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }

}

bfs和dfs的板子

图和二叉树的宽搜最大的不同的就是,图是可能有环的。二叉树是没环的,所以图可能死循环卡住,所以需要额外记录是否有访问过,一般是哈希表或者数组。
深搜是点入栈之前就需要处理了,广搜是点入队列之后开始处理。


public static void bfs(Node node){
    if(node==null) return;
    Queue<Node> queue = new LinkedList<>();
    HashSet<Node> set = new HashSet<>();
    queue.add(node);
    set.add(node);
    while(!queue.isEmpty()){
        Node cur = queue.poll();
        /*  具体的处理逻辑
            (宽搜一般是结点入队列后再处理)
        */
        for(Node next: cur.nexts){
            if(!set.contains(next)){//如果set中没有,那么说明这个next结点没有被访问过
            queue.add(next);//扔到队列里
            set.add(next);//并且标记访问
            }
        }
    }
}

public static void dfs(Node node){
    if(node==null) return;
    Stack<Node> stack = new Stack<>();
    HashSet<Node> set = new HashSet<>();
    stack.add(node);
    set.add(node);
    /*具体的处理逻辑(深搜一般是结点入栈前就进行处理)*/
    while(!stack.isEmpty()){
        Node cur = stack.pop();
        for(Node next:cur.nexts){
            if(!set.contains(next)){
                stack.push(cur);//在这里需要把cur和next两个结点同时入栈是因为
                stack.push(next);//想在栈里保持深度搜索的路径。这次搜索相比于上一次搜索,在栈中就多了一个next结点。
                set.add(cur);
                set.add(next);
                /*具体的处理逻辑 */
                break;//之所以立马break是因为深搜每次只走一步,不像宽搜每次走一层。
            }
        }
    }
}

题目

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。

class Node {
public int val;
public List neighbors;
}

测试用例格式:

简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1(val = 1),第二个节点值为 2(val = 2),以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
在这里插入图片描述
输入:adjList = [[2,4],[1,3],[2,4],[1,3]]
输出:[[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点。
节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
节点 4 的值是 4,它有两个邻居:节点 1 和 3 。

示例 2:
输入:adjList = [[]]
输出:[[]]
解释:输入包含一个空列表。该图仅仅只有一个值为 1 的节点,它没有任何邻居。
示例 3:

输入:adjList = []
输出:[]
解释:这个图是空的,它不含任何节点。

提示:

节点数不超过 100 。
每个节点值 Node.val 都是唯一的,1 <= Node.val <= 100。
无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
图是连通图,你可以从给定节点访问到所有节点。

思路

图的深拷贝可以由dfs或者bfs实现。但是需要注意:在这里的set不再是HashSet,因为它不是存储这个节点是否访问过。而是直接存储原节点和克隆节点的地址的键值对。因为图是无向图,或者说,双向图,所以访问过的节点也可能要再次处理的。譬如节点1的邻居是节点2,那么我们遍历节点1时,会增加“节点1->节点2”。但是如果只是看是否访问过时,遍历到节点2时就会因为访问过节点1而丧失掉“节点2->节点1”的这条边。


这道题用bfs会好一点。因为它是个存在环的无向图,bfs不存在回溯的情况,可以保证每个节点只被遍历一次,譬如遍历到节点1
时,直接构建节点1和其原有邻居列表的邻居关系,那么节点1为出发点的所有单边情况都构建好了。之后分别遍历到节点2和节点4时,也会将节点1为接受点的所有单边情况都构建好。所以刚好双边都能不多不少不重不漏地构建完。


但是dfs不同,因为dfs的每个节点不止会被只遍历一次,因为它要回溯。所以可能出现邻居节点重复添加的情况,所以构建邻居关系时比bfs需要多一步判重。
譬如开始时节点1先克隆并入栈。它原来的邻居节点有节点2和节点4,因为节点2没有被克隆过,所以开始遍历节点2。

节点2遍历时,它原来的邻居节点有节点1和节点3,因为节点1被克隆过,所以会构建“节点2->节点1”的邻居关系。但是因为节点3没有被克隆过,所以开始遍历节点3。

==节点3遍历时,原有邻居有节点2和节点4,因为节点2被克隆过,所以会构建“节点3->节点2”==的邻居关系,但是因为节点4没有被克隆过,所以开始遍历节点4.。

节点4遍历时,原有邻居有节点3和节点1,因为节点1被克隆过,所以会构建“节点4->节点1”的邻居关系。同时节点3也被克隆过所以会构建“节点4->节点3”的邻居关系。然后开始遍历节点3。
节点3遍历时,原有邻居有节点2和节点4,因为节点2被克隆过,所以如果不判重,会多构建一个“节点3->节点2”的邻居关系。

bfs代码

class Solution {
    public Node cloneGraph(Node node) {
        if(node==null) return node;//直接返回node就好了,因为是空指针。
        HashMap<Node, Node> set = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        set.put(node, cloneNode(node));
        queue.add(node);
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            for(Node next: cur.neighbors){
                if(!set.containsKey(next)){//如果这个节点没有被克隆过
                    queue.add(next);//说明没有被遍历过,直接加入队列
                    set.put(next, cloneNode(next));//并加入set
                }
            set.get(cur).neighbors.add(set.get(next));//不管有没有被克隆过,因为每个节点只会被遍历一次,那么它的邻居节点都需要一次性加入该节点的邻居列表中。同时注意不是直接set.get(cur).neighbors.add(next),而是set中next的克隆地址。
            }
        }
    return set.get(node);
    }
//这个函数,单纯地实现克隆功能,不连接邻居关系。
    private Node cloneNode(Node node){
        return new Node(node.val, new ArrayList<>());
    }
}

26ms,击败25.12%使用 Java 的用户

说实话,待优化……

dfs代码

class Solution {
    public Node cloneGraph(Node node) {
        if(node==null) return node;
        HashMap<Node, Node> set = new HashMap<>();
        Stack<Node> stack = new Stack<>();
        set.put(node,cloneNode(node));
        stack.add(node);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            for(Node next: cur.neighbors){
                if(!set.containsKey(next)){//如果这个next节点没有被克隆过
                    stack.add(cur);//说明也没有被遍历过,为了不会回退到上次遍历过的节点,cur和next依次加入栈。
                    stack.add(next);
                    set.put(next,cloneNode(next)); //克隆next节点,放入set
                    break;
                }
                List<Node> list = set.get(cur).neighbors;//如果这个next节点已经有克隆过了,那么看是否需要构建当前节点和next节点的邻居关系
                if(!list.contains(set.get(next))) set.get(cur).neighbors.add(set.get(next));//如果之前已经有过当前节点和next节点的邻居关系,说明我们不是第一次遍历到当前节点,而是回溯过程中遇到的当前节点,所以不再需要构建邻居关系。
            }
        }
        return set.get(node);
    }

    public Node cloneNode(Node node){
        return new Node(node.val, new ArrayList<>());
    }
}

27ms,击败15.19%使用 Java 的用户

依旧待优化……

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/371291.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于springboot地方美食分享网站源码和论文

基于springboot地方美食分享网站源码和论文361 首先&#xff0c;论文一开始便是清楚的论述了系统的研究内容。其次&#xff0c;剖析系统需求分析&#xff0c;弄明白“做什么”&#xff0c;分析包括业务分析和业务流程的分析以及用例分析&#xff0c;更进一步明确系统的需求。然…

基于微信小程序的书籍阅读系统,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

STM32F407移植OpenHarmony笔记9

继上一篇笔记&#xff0c;已经完成liteos内核的基本功能适配。 今天尝试启动OHOS和XTS兼容性测试。 如何启动OHOS&#xff1f; OHOS系统初始化接口是OHOS_SystemInit(void)&#xff0c;在内核初始化完成后&#xff0c;就能调用。 extern void OHOS_SystemInit(void); OHOS_Sys…

【数据分享】1929-2023年全球站点的逐年降雪深度数据(Shp\Excel\免费获取)

气象数据是在各项研究中都经常使用的数据&#xff0c;气象指标包括气温、风速、降水、能见度等指标&#xff0c;说到气象数据&#xff0c;最详细的气象数据是具体到气象监测站点的数据&#xff01; 之前我们分享过1929-2023年全球气象站点的逐年平均气温数据、逐年最高气温数据…

「优选算法刷题」:计算布尔二叉树的值

一、题目 给你一棵 完整二叉树 的根&#xff0c;这棵树有以下特征&#xff1a; 叶子节点 要么值为 0 要么值为 1 &#xff0c;其中 0 表示 False &#xff0c;1 表示 True 。非叶子节点 要么值为 2 要么值为 3 &#xff0c;其中 2 表示逻辑或 OR &#xff0c;3 表示逻辑与 AND…

1.0 Hadoop 教程

Hadoop 是一个开源的分布式计算和存储框架&#xff0c;由 Apache 基金会开发和维护。 Hadoop 为庞大的计算机集群提供可靠的、可伸缩的应用层计算和存储支持&#xff0c;它允许使用简单的编程模型跨计算机群集分布式处理大型数据集&#xff0c;并且支持在单台计算机到几千台计…

HBase相关面试准备问题

为什么选择HBase 1、海量存储 Hbase适合存储PB级别的海量数据&#xff0c;在PB级别的数&#xff0c;能在几十到几百毫秒内返回数据。这与Hbase的极易扩展性息息相关。正是因为Hbase良好的扩展性&#xff0c;才为海量数据的存储提供了便利。 2、列式存储 这里的列式存储其实说的…

【Android】RxJava系列01-基本概述和基本用法

少年啊&#xff0c;要永远相信美好的事情即将发生 【Android】RxJava系列01-基本概述和基本用法 1.RxJava的概述2.RxJava的作用3.观察者和被观察者4.背压5.RxJava的基本用法步骤一&#xff0c;创建Observer&#xff08;观察者&#xff09;步骤二&#xff0c;创建Observable&…

LangChain 最近发布的一个重要功能:LangGraph

LangGraph 是 LangChain 最近发布的一个重要功能&#xff0c;LangChain 进入多代理框架领域。通过建立在LangChain 之上&#xff0c;LangGraph 使开发人员可以轻松创建强大的代理运行时。 LangChain 使用其表达语言&#xff08;LCEL&#xff09;为开发人员构建定制链提供技术支…

深度学习(7)---Diffusion Model概念讲解

文章目录 一、基本概括1.1 概念讲解1.2 Denoise模块 二、Stable Diffusion2.1 概念讲解2.2 FID2.3 CLIP 一、基本概括 1.1 概念讲解 1. Diffusion Model是一种生成模型&#xff0c;通过连续添加高斯噪声来破坏训练数据&#xff0c;然后学习反转的去噪过程来恢复数据。它分为正…

go消息队列RabbitMQ - 订阅模式-fanout

1、发布订阅 订阅模式&#xff0c;消息被路由投递给多个队列&#xff0c;一个消息被多个消费者获取。 1&#xff09; 可以有多个消费者 2&#xff09; 每个消费者有自己的queue&#xff08;队列&#xff09; 3&#xff09; 每个队列都要绑定到Exchange&#xff08;交换机&…

【npm】安装全局包,使用时提示:不是内部或外部命令,也不是可运行的程序或批处理文件

问题 如图&#xff0c;明明安装Vue是全局包&#xff0c;但是使用时却提示&#xff1a; 解决办法 使用以下命令任意一种命令查看全局包的配置路径 npm root -g 然后将此路径添加到环境变量中去&#xff0c;这里注意&#xff0c;原本NodeJS的安装路径配置的环境变量不要删除&…

Sklearn、TensorFlow 与 Keras 机器学习实用指南第三版(一)

原文&#xff1a;Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 前言 机器学习海啸 2006 年&#xff0c;Geoffrey Hinton 等人发表了一篇论文&#xff0c;展示了如何训练一个能够以最先进的精度…

Tomcat组件架构与数据流

一、背景与简介 Tomcat我们都知道是一个开源的、实现了大部分Java EE、Servlet、JSP规范的Servlet容器, 允许我们将实现了Serlvet接口的Web程序war包进行部署运行。 但是你有对Tomcat做过细致的学习么? 我相信大部分同学和我一样&#xff0c;之前也是只会进行简单使用&#x…

IDEA插件ChatGPT - Easycode安装使用

IDEA插件ChatGPT - Easycode简介 ChatGPT - Easycode 是一个由 OpenAI 开发的 IntelliJ IDEA 插件&#xff0c;它可以利用 ChatGPT 的强大语言生成能力&#xff0c;帮助开发人员提高编码效率。 主要功能&#xff1a; 代码生成&#xff1a;可以根据自然语言描述生成代码&…

sqli-labs-master靶场训练笔记(21-38|精英级)

2024.1.30 level-21 (cookie 注入数据加密) 从页面上就可以看出这次的数据被 baes64 加密了 中国有句古话&#xff1a;师夷长技以制夷 &#xff0c;用base64加密后的数据即可爆出数据 加密前&#xff1a; admin and updatexml(1,concat(~,(select database()),~),1) and …

ReactNative实现宽度变化实现的动画效果

效果如上图所示&#xff0c;通过修改设备宽度实现动画效果 import React, {useRef, useEffect, useState} from react; import {Animated, Text, View, Image} from react-native;const FadeInView props > {const fadeAnim useRef(new Animated.Value(0)).current;React…

item_get_video-获取视频详情(bili.item_get_video)

B站&#xff08;Bilibili&#xff09;的item_get_video API用于获取视频的详细信息。通过调用该API&#xff0c;您将能够获得视频的基本信息、元数据、播放链接等。这使得开发者可以轻松地将B站视频集成到自己的应用程序或网站中&#xff0c;为用户提供更丰富的内容和更好的体验…

vue项目集成booststrap

1.首先安装bootstrap npm install bootstrap 我安装的是4.3的版本 2.在main.js中引用bootstrap import bootstrap/dist/css/bootstrap.css import bootstrap/dist/css/bootstrap.min.css import bootstrap/dist/js/bootstrap.js import bootstrap/dist/js/bootstrap.min.…

新数据不影响原来的数据

问题描述 新数据修改时&#xff0c;原来的数据也会受影响 const obj1 ref({ name: slx, age: 20 })const obj2 obj1obj2.value.name hhhhconsole.log(obj1, obj1.value)console.log(obj2, obj2.value)解决方法 (仅适用于对象 在这段代码中&#xff0c;obj1 和 obj2 指向同…