数据结构--图的遍历 DFS
数据结构–图的遍历 DFS
树的深度优先遍历
//树的先根遍历
void PreOrder(TreeNode *R)
{if(R != NULL){visit(R); //访问根节点while(R还有下一个子树T)PreOrder(T);//先根遍历下一棵子树}
}
图的深度优先遍历
bool visited [MAX_VERTEX_NUM]; //访问标记数组
void DFS(Graph G, int v) //从顶点v出发,深度优先遍历图
{visit(v);//访问顶点visited[v] = TRUE; //设已访问标记{for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighor(G, v, w))if(!visited[w]) //w为u的尚未访问的邻接顶点DFS(G, w);}
}
如果是⾮连通图,则⽆法遍历完所有结点
bool visited[MAX_VERTEX_NUM]; //访问标记数组void DFSTraverse(Graph G)//对图G进行深度优先遍历
{for(v = 0; v < G.vexnum; ++v)visited[v] = FALSE;//初始化已访问标记数据for(v = 0; v < G.vexnum; ++v)if(!visited[v])DFS(G, v);//本代码中是从v=0开始遍历
}void DFS(Graph G, int v) //从顶点v出发,深度优先遍历图G
{visit(v);//访问顶点vvisited[v] = TRUE; //设已访问标记for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighor(G, v, w))if(!visited[w]) //w为u的尚未访问的邻接顶点DFS(G,w);
}
复杂度分析
空间复杂度:来⾃函数调⽤栈,最坏情况,递归深度为 O ( ∣ V ∣ ) \color{red}空间复杂度:来⾃函数调⽤栈,最坏情况,递归深度为O(|V|) 空间复杂度:来⾃函数调⽤栈,最坏情况,递归深度为O(∣V∣)
空间复杂度:最好情况, O ( 1 ) \color{purple}空间复杂度:最好情况,O(1) 空间复杂度:最好情况,O(1)
时间复杂度=访问各结点所需时间+探索各条边所需时间
邻接矩阵 \color{red}邻接矩阵 邻接矩阵存储的图:
访问 |V| 个顶点需要O(|V|)的时间
查找每个顶点的邻接点都需要O(|V|)的时间,⽽总共有|V|个顶点
时间复杂度= O ( ∣ V ∣ 2 ) \color{red}O(|V|^2) O(∣V∣2)
邻接表 \color{red}邻接表 邻接表存储的图:
访问 |V| 个顶点需要O(|V|)的时间
查找各个顶点的邻接点共需要O(|E|)的时间,
时间复杂度= O ( ∣ V ∣ + ∣ E ∣ ) \color{red}O(|V|+|E|) O(∣V∣+∣E∣)
注:
同⼀个图的 邻接矩阵 \color{red}邻接矩阵 邻接矩阵表示⽅式 唯⼀ \color{red}唯⼀ 唯⼀,因此 深度优先遍历序列唯⼀ \color{red}深度优先遍历序列唯⼀ 深度优先遍历序列唯⼀
同⼀个图 邻接表 \color{red}邻接表 邻接表表示⽅式 不唯⼀ \color{red}不唯⼀ 不唯⼀,因此 深度优先遍历序列不唯⼀ \color{red}深度优先遍历序列不唯⼀ 深度优先遍历序列不唯⼀
深度优先⽣成树
同⼀个图的邻接矩阵表示⽅式唯⼀,因此深度优先遍历序列唯⼀,深度优先⽣成树也唯⼀
同⼀个图邻接表表示⽅式不唯⼀,因此深度优先遍历序列不唯⼀,深度优先⽣成树也不唯⼀
深度优先⽣成森林
图的遍历与图的连通性
对 ⽆向图 \color{red}⽆向图 ⽆向图进⾏BFS/DFS遍历
调⽤BFS/DFS函数的次数=连通分量数
对于 连通图 \color{red}连通图 连通图,只需调⽤1次 BFS/DFS
对 有向图 \color{red}有向图 有向图进⾏BFS/DFS遍历
调⽤BFS/DFS函数的次数要具体问题具体分析
若起始顶点到其他各顶点都有路径,则只需调⽤1次
BFS/DFS 函数
对于 强连通图 \color{red}强连通图 强连通图,从任⼀结点出发都只需调⽤1次 BFS/DFS
知识回顾与重要考点
相关文章:
数据结构--图的遍历 DFS
数据结构–图的遍历 DFS 树的深度优先遍历 //树的先根遍历 void PreOrder(TreeNode *R) {if(R ! NULL){visit(R); //访问根节点while(R还有下一个子树T)PreOrder(T);//先根遍历下一棵子树} }图的深度优先遍历 bool visited [MAX_VERTEX_NUM]; //访问标记数组 void DFS(Grap…...
SpringBoot集成MyBatisPlus+MySQL(超详细)
前言 查看此文章前强烈建议先看这篇文章:Java江湖路 | 专栏目录 该文章纪录的是SpringBoot快速集成MyBatis Plus,每一步都有记录,争取每一位看该文章的小伙伴都能操作成功。达到自己想要的效果~ 文章目录 前言1、什么是MyBatisPlus2、Spring…...
一边是计算机就业哀鸿遍野,一边是高考生疯狂涌向计算机专业
在张雪峰推荐的几大专业里,计算机专业是其中之一。近几年,计算机专业报考热度不减,但就业前景却令人堪忧,互联网裁员接二连三,许多码农找不到工作。 一位网友感叹:一边是计算机就业哀鸿遍野,一…...
解决外部主机无法访问Docker容器的方法
使用Docker启动了一个tomcat容器,并做了端口映射,但是外部主机仍然无法访问。 编辑centos上的配置文件 vi /etc/sysctl.conf net.ipv4.ip_forward1 systemctl restart network保存以后即可生效,这个配置是开启linux的ip数据包转发功能&#…...
IDEA中修改类头的文档注释信息
IDEA中修改类头的文档注释信息 选择File--Settings--Editor--File and Code Templates--Includes,可以把文档注释写成这种的 /**author: Arbicoralcreate: ${YEAR}-${MONTH}-${DAY} ${TIME}Description: */这样回看就可以很清楚的看到自己创建脚本的时间ÿ…...
建模教程:如何利用3ds Max 和 After Effects 实现多通道渲染和后期合成
推荐: NSDT场景编辑器 助你快速搭建可二次开发的3D应用场景 1. 创建基本场景 步骤 1 打开 3ds Max。 打开 3ds Max。 步骤 2 我做了一个简单的场景。我放了三个 彼此之间有一定距离的物体。 制作对象 步骤 3 按 Ctrl-C 键 在透视视图中创建摄影机。 创建相机 …...
JPA之Hibernate
JPA 定义:是 JavaEE 中一组用于持久化数据的 API,它提供了一种标准的 ORM 规范,用于 Java 对象映射到数据库中。 JPA 的开发是为了简化企业级应用程序的开发,降低应用程序与数据库之间的耦合度,并提高应用程序的可维护…...
leetcode(力扣)剑指 Offer 16. 数值的整数次方 (快速幂)
文章目录 题目描述思路分析完整代码 题目描述 实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。 示例 1: 输入:x 2.00000, n 10 输出:10…...
git命令分类合集
配置 git config --global user.name <name>:设置全局用户名 git config --global user.email <email>:设置全局用户邮箱 git config --global core.editor <editor>:设置全局文本编辑器创建与克隆仓库 git init…...
微信小程序打开地图的方法
1、打开内置地图 wx.openLocation({latitude: 31.230416, // 上海的纬度longitude: 121.473701, // 上海的经度name: 上海市, // 地点名称address: 中国上海市黄浦区人民广场, // 地址的详细说明scale: 18, // 缩放比例success: function(res) {console.log(打开地图成功);},f…...
快手头部主播合体,二驴祁天道直播首秀销售额破亿
2023年刚刚过半,直播江湖突然生变。 快手头部娱乐主播「二驴」与快手户外主播第一人「祁天道」宣布“合体”,两者加总的粉丝量接近1亿,又一个“超级网红IP”诞生。 ▲图源:二驴的、祁天道快手截图 从白手起家的草根,…...
Golang Devops项目开发(1)
1.1 GO语言基础 1 初识Go语言 1.1.1 开发环境搭建 参考文档:《Windows Go语言环境搭建》 1.2.1 Go语言特性-垃圾回收 a. 内存自动回收,再也不需要开发人员管理内存 b. 开发人员专注业务实现,降低了心智负担 c. 只需要new分配内存,…...
Django系列之DRF简单使用
基于ModelViewSets的简单使用 models.py from django.db import modelsclass AuthorDetail(models.Model):gender models.CharField(max_length8)birthday models.DateField()telephone models.BigIntegerField()addr models.CharField(max_length64)class Author(models…...
新闻标题文本分类任务
目录 知识回顾使用debug调试 知识回顾 预处理内容 文本主要进行清洗、分词/分字 ID替换(不希望计算机看到文字,而是ID),通过语料表来表示,根据频率高低来分配ID号 文本的ID映射到文本的一个特征向量,进行词嵌入(Embedding)&…...
自己实现MyBatis 底层机制--抽丝剥茧(上)
😀前言 本篇博文是学习过程中的笔记和对于MyBatis底层机制的分析思路,希望能够给您带来帮助😊 🏠个人主页:晨犀主页 🧑个人简介:大家好,我是晨犀,希望我的文章可以帮助到…...
Django后端执行成功或失败状态码
后端执行成功或失败以状态码的形式告诉前端,处理成功返回200系列状态码,执行前端then里面的代码;处理失败返回400/500系列状态码,执行catch里面的代码。 200 OK :服务器成功返回用户请求的数据 201 CREATED ÿ…...
Prometheus中的关键设计
1、标准先行,注重生态 Prometheus 最重要的规范就是指标命名方式,数据格式简单易读。比如,对于应用层面的监控,可以要求必须具备这几个信息。 指标名称 metric Prometheus 内置建立的规范就是叫 metric(即 __name__…...
Centos7 安装yum
1、检查主机名和网络并且配置/etc/hosts文件 查看主机名:hostname 查看ip :ifconfig vi /etc/hosts//添加把主机名和IP配置进去hosts文件192.18.56.111 orcale12c2、关闭防火墙 systemctl status firewalld.service//检查防火墙状态 暂时关闭防火墙,下…...
无涯教程-Lua - 简介
Lua是一种轻量语言,它的官方版本只包括一个精简的核心和最基本的库。这使得Lua体积小、启动速度快。它用ANSI C语言编写并以源代码形式开放,编译后仅仅一百余K,可以很方便的嵌入别的程序里。和许多“大而全”的语言不一样,网络通信…...
【第一阶段】kotlin语言引用数据类型
Java语言中有两种数据类型 第一种:基本数据类型 如int double等 第二种:引用数据类型。如String kotlin只有一种数据类型,看起来都是引用数据类型,实际上编译器会在Java字节码中,修改成基本类型 //Java语言中有两种数…...
微信聊天记录永久保存与深度分析:WeChatMsg让你的数字记忆不再流失
微信聊天记录永久保存与深度分析:WeChatMsg让你的数字记忆不再流失 【免费下载链接】WeChatMsg 提取微信聊天记录,将其导出成HTML、Word、CSV文档永久保存,对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trend…...
告别内存映射:用AXI-Stream协议搞定FPGA视频流传输(附时序图解析)
告别内存映射:用AXI-Stream协议搞定FPGA视频流传输(附时序图解析) 在FPGA视频处理系统中,数据流的传输效率往往成为性能瓶颈。传统的内存映射方式虽然通用,但对于高吞吐量的视频数据流却显得力不从心。AXI-Stream协议以…...
OFA模型在VMware虚拟机中的开发测试环境搭建
OFA模型在VMware虚拟机中的开发测试环境搭建 对于很多刚接触AI模型开发的个人开发者或学生来说,最大的门槛往往不是算法本身,而是硬件。一块性能足够的独立GPU价格不菲,让很多人在起步阶段就望而却步。难道没有物理GPU,就真的没法…...
TDengine IDMP 工业数据建模 —— 数据标准化
3.4 数据标准化 工业环境通常从多个数据源采集数据,这些数据往往命名不一致、物理单位各异、数据结构不同。如果没有标准化,跨资产分析、AI 生成洞察和数据汇聚将变得不可靠甚至无法实现。TDengine IDMP 提供了多种机制,对整个资产模型中的数…...
终极URL标准完整指南:从基础概念到实战应用
终极URL标准完整指南:从基础概念到实战应用 【免费下载链接】url URL Standard 项目地址: https://gitcode.com/gh_mirrors/url/url URL(统一资源定位符)是互联网的基石,每一个网页、图片、视频都通过URL来定位和访问。URL…...
别再只盯着EMD了!滚动轴承故障诊断,试试VMD和MCKD这些新方法(附Python代码对比)
滚动轴承故障诊断:VMD与MCKD的实战对比与Python实现 滚动轴承作为旋转机械的核心部件,其健康状态直接影响设备运行安全。传统经验模态分解(EMD)虽广泛应用,但在处理强噪声和非平稳信号时存在明显局限。本文将深入解析变…...
使用ZLMRTCClient.j实现webRtc流播放
1. 核心播放器组件封装 (WebRTCPlayer.vue)为了在项目中复用播放逻辑,我们首先封装一个 WebRTCPlayer 组件。该组件主要负责:初始化播放器实例:配置 ZLMRTCClient.Endpoint。处理自动播放:解决浏览器禁止带音频自动播放的问题。生…...
ClawdBot代码实例:修改clawdbot.json实现模型热切换实操
ClawdBot代码实例:修改clawdbot.json实现模型热切换实操 1. 引言:你的个人AI助手,想换模型就换模型 想象一下,你有一个24小时在线的AI助手,它能帮你写代码、回答问题、整理文档。但用久了,你可能会想&…...
DanKoe 视频笔记:深度工作:改变生活的常规 [特殊字符]
在本教程中,我们将学习一套能极大提升专注力与生产力的深度工作常规。这套方法的核心在于理解并管理你的注意力,将其视为最宝贵的资源,并像管理计算机内存一样去优化它。我们将从核心概念开始,逐步拆解具体步骤,帮助你…...
7大维度测评:2023年开源付费墙绕过工具终极选择指南
7大维度测评:2023年开源付费墙绕过工具终极选择指南 【免费下载链接】bypass-paywalls-chrome-clean 项目地址: https://gitcode.com/GitHub_Trending/by/bypass-paywalls-chrome-clean 在数字内容访问需求日益增长的今天,选择一款高效可靠的开源…...
