数据结构—图的遍历
6.3图的遍历
遍历定义:
从已给的连通图中某一顶点出发,沿着一些边访问遍历图中所有的顶点,且使每个顶点仅被访问一次,就叫作图的遍历,它是图的基本运算。
遍历实质:找每个顶点的邻接点的过程。
图的特点:
图中可能存在回路,且图的任一顶点都可能与其他顶点相通,在访问某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
怎样避免重复访问?
解决思路:设置辅助数组visited[n],用来标记每个被访问过的顶点。
- 初始状态visited[i]为0
- 顶点i被访问,改visited[i]为1,防止被多次访问
图常用的遍历:
- 深度优先搜索(Depth First Search——DFS)
- 广度优先搜索(Breadth Frist Search——BFS)
6.3.1深度优先遍历(DFS)
方法:
- 在访问图中某一起始顶点v后,由v出发,访问它的任一邻接顶点w1;
- 再用w1出发,访问与w1邻接但还未被访问过的顶点w2;
- 然后再从w2出发,进行类似的访问,…
- 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。
- 接着,退回一步,退到前一次刚访问过的顶点,看是否还有其他没有被访问的邻接顶点。
- 如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;
- 如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。
例如:

连通图的深度优先遍历类似于树的先根遍历
6.3.2深度优先搜索遍历算法实现
邻接矩阵无向图深度遍历实现(连通图)

void DFS(AMGraph G,int v){//图G为邻接矩阵类型cout<<v;visited[v]=true;//访问第v个顶点for(w=0;w<G.vexnum;w++)//依次检查邻接矩阵v所在的行if((G.arcs[v][w]!=0)&&(!visited[w]))DFS(G,w);//w是v的邻接点,如果w未访问,则递归调用DFS
}
DFS算法效率分析
- 用邻接矩阵来表示图,遍历图中每一个顶点都要从头扫描该顶点所在行,时间复杂度为O(n2)。
- 用邻接表来表示图,虽然有2e个表结点,但只需扫描e个结点即可完成遍历,加上访问n个头结点的时间,时间复杂度为O(n+e)。
结论:
- 稠密图适于在邻接矩阵上进行深度遍历;
- 稀疏图适于在邻接表上进行深度遍历。
非连通图的遍历

6.3.3广度优先搜索(BFS)
方法:从图的某一结点出发,首先依次访问该结点的所有邻接点v1,v2,…,vn再按这些顶点被访问的先后次序依次访问与他们相邻接的所有未被访问的顶点。
重复此过程,直至所有顶点均被访问为止。

非连通图的广度遍历

顶点访问次序:a c d e f h k b g

void BFS(Graph G,int v){//按广度优先非递归遍历连通图Gcout<<v;visited[v]=true;//访问第v个顶点InitQueue(Q);//辅助队列Q初始化,置空EnQueue(Q,v);//v进队while(!QueueEmpty(Q)){//队列非空DeQueue(Q,u);//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))if(!visited[w]){//w为u的尚未访问的邻接顶点cout<<w;visited[w]=true;EnQueue(Q,w);//w进队}}
}
BFS算法效率分析
- 如果使用邻接矩阵,则BFS对于每一个被访问到的顶点,都要循环检测矩阵中的整整一行(n个元素),总的时间代价为O(n2)。
- 用邻接表来表示图,虽然有2e个表结点,但只需扫描e个结点即可完成遍历,加上访问n个头结点的时间,时间复杂度为O(n+e)。
6.3.4DFS和BFS算法效率比较
- 空间复杂度相同,都是O(n)(借用了堆栈或队列);
- 时间复杂度只与存储结构(邻接矩阵或邻接表)有关,而与搜索路径无关。
相关文章:
数据结构—图的遍历
6.3图的遍历 遍历定义: 从已给的连通图中某一顶点出发,沿着一些边访问遍历图中所有的顶点,且使每个顶点仅被访问一次,就叫作图的遍历,它是图的基本运算。 遍历实质:找每个顶点的邻接点的过程。 图的…...
MySQL主从复制基于二进制日志的高可用架构指南
前言 在现代数据库架构中,MySQL主从复制技术扮演着重要角色。它不仅可以提升数据库性能和可扩展性,还赋予系统卓越的高可用性和灾难恢复能力。本文将深入剖析MySQL主从复制的内部机制,同时通过一个实际案例,展示其在实际场景中的…...
RestTemplate HTTPS请求忽略SSL证书
问题描述 使用RestTemplate发送HTTPS请求的时候,出现了这样的一个问题: sun.security.validator.ValidatorException: PKIX path building failed: sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification …...
Jenkins触发器时间、次数设定
触发器触发条件介绍 触发器触发条件公式:由5颗星组成 * * * * * 分别代表:分钟(0-59) 小时(0-23) 日期(1-31) 月份(1-12) 星期(0-6) 企业项目中常用场景介绍 场景1:接口脚本部分测试通过,部分还在进行,回归测试脚本执行…...
kafka partition的数据文件(offffset,MessageSize,data)
partition中的每条Message包含了以下三个属性: offset,MessageSize,data,其中offset表示Message在这个partition中的偏移量,offset不是该Message在partition数据文件中的实际存储位置,而是逻辑上一个值&…...
htnl根据轮播图图片切换背景色
htnl根据轮播图图片切换背景色 <!DOCTYPE html> <html><head><meta charset"UTF-8"><title>轮播图示例</title><link rel"stylesheet" href"https://cdn.jsdelivr.net/npm/swiper10/swiper-bundle.min.css&q…...
gpu-manager安装及测试
提示:GPU-manager安装为主部分内容做了升级开箱即用,有用请点收藏❤抱拳 文章目录 前言一、约束条件二、使用步骤1.下载镜像1.1 查看当前虚拟机的驱动类型: 2.部署gpu-manager3.部署gpu-admission4.修改kube-scheduler.yaml![在这里插入图片描…...
Go和Java实现享元模式
Go和Java实现享元模式 下面通过一个实例来说明享元模式的使用。 1、享元模式 享元模式主要用于减少创建对象的数量,以减少内存占用和提高性能。这种类型的设计模式属于结构型模式,它提 供了减少对象数量从而改善应用所需的对象结构的方式。 享元模式…...
Zookeeper特性与节点数据类型详解
CAP&Base理论 CAP理论 cap理论是指对于一个分布式计算系统来说,不可能满足以下三点: 一致性 : 在分布式环境中,一致性是指数据在多个副本之间是否能够保持一致的 特性,等同于所有节点访问同一份最新的数据副本。在一致性的需…...
函数的递归
1、什么是递归? 程序调用自身的编程技巧称为递归。 递归作为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解&#x…...
Android T 窗口层级其二 —— 层级结构树的构建(更新中)
如何通过dump中的内容找到对应的代码? 我们dump窗口层级发现会有很多信息,adb shell dumpsys activity containers 这里我们以其中的DefaultTaskDisplayArea为例 在源码的framework目录下查找该字符串,找到对应的代码就可以通过打印堆栈或者…...
ASIC芯片设计全流程项目实战课重磅上线 ,支持 65nm制程流片 !
全流程项目实战课学什么? 此次推出【 ASIC芯片设计全流程项目实战课】,基于IPA图像处理加速器,以企业级真实ASIC项目为案例,学员可参与全流程项目实践,以及65nm真实流片! 众所周知,放眼整个IC硕…...
背上沉重的书包准备run之react篇
沉重,太沉重了。。。没理好捏,等我脑子歇歇再好好补充一下 react特性? React 是一个用于构建用户界面的 JavaScript 库,它具有以下特性: 组件化开发:React 基于组件化思想,将 UI 拆分为独立、…...
LAMP及论坛搭建
一、概述 LAMP架构是目前成熟的企业网站应用模式之一,指的是协同工作的一整套系统和相关软件,能够提供动态Web站点服务及其应用开发环境。LAMP是一个缩写词,具体包括Linux操作系统、Apache网站服务器、MySQL数据库服务器、PHP(或…...
php-cgi.exe - FastCGI 进程超过了配置的请求超时时限
解决方案一: 处理(php-cgi.exe - FastCGI 进程超过了配置的请求超时时限)的问题 内容转载: 处理(php-cgi.exe - FastCGI 进程超过了配置的请求超时时限)的问题_php技巧_脚本之家 【详细错误】: HTTP 错误 500.0 - Internal Server Error C:…...
linux系统虚拟主机开启支持SourceGuardian(sg11)加密组件
注意:sg11我司只支持linux系统虚拟主机自主安装。支持php5.3及以上版本。 1、登陆主机控制面板,找到【远程文件下载】这个功能。 2、远程下载文件填写http://download.myhostadmin.net/vps/sg11_for_linux.zip 下载保存的路径填写/others/ 3、点击控制…...
让我们一起探讨汽车充电桩控制主板的应用
你是否想过,你的汽车充电桩可以更智能?可以支持更多类型的电池,更多操作系统,更多协议和更多电源?让我们一起探讨汽车充电桩控制主板的应用。 控制主板是充电桩的大脑,它可以应用于各种充电桩,包括智能充电桩、电动汽…...
Gartner发布《2023年全球RPA魔力象限》:90%RPA厂商,将提供生成式AI自动化
8月3日,全球著名咨询调查机构Gartner发布了《2023年全球RPA魔力象限》,通过产品能力、技术创新、市场影响力等维度,对全球16家卓越RPA厂商进行了深度评估。 弘玑Cyclone(Cyclone Robotics)、来也(Laiye&am…...
springboot整合JMH做优化实战
这段时间接手项目出现各种问题,令人不胜烦扰。吐槽下公司做项目完全靠人堆,大上快上风格注定留下一地鸡毛,修修补补不如想如何提升同事代码水准免得背锅。偶然看到关于JMH对于优化java代码的直观性,于是有了这篇文章,希…...
利用ffmpeg分析视频流
ffprobe -show_packets -i "rtsp://192.168.61.46:8554/live?channel0&type0":该命令用于显示 RTSP 流中的数据包信息,例如时间戳、大小、持续时间等。 ffprobe -i "rtsp://192.168.61.46:8554/live?channel0&type0"&…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...
2.3 物理层设备
在这个视频中,我们要学习工作在物理层的两种网络设备,分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间,需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质,假设A节点要给…...
比特币:固若金汤的数字堡垒与它的四道防线
第一道防线:机密信函——无法破解的哈希加密 将每一笔比特币交易比作一封在堡垒内部传递的机密信函。 解释“哈希”(Hashing)就是一种军事级的加密术(SHA-256),能将信函内容(交易细节…...
