当前位置: 首页 > news >正文

6.3图的遍历

图的遍历是指从某点出发,按照某种搜索方式沿着边访问图中所有节点

图的遍历算法主要有两种:广度优先,深度优先

都需要辅助数组visited[]来记录节点是否被访问过

6.3.1广度优先搜索

like层次遍历,需要辅助队列

代码实现


#include<stdio.h>
#define maxnum 15
bool visited[maxnum];//定义辅助数组
void BFSTraverse(Graph G) {for (int i = 0; i < G.vexnum; i++){visited[i] = false;}//初始化数组initQueue(Q);//初始化队列for (int i = 0; i < G.vexnum; i++)//从0号顶点开始遍历{if (!visited[i]) {BFS(G,i);//广度优先遍历}}
}
void BFS(Graph G,int i){visit(i);//访问visited[i] = true;//改为tEnQueue(Q,i);//入队while (!isEmpty(Q)) {//判断队列是否为空DeQueue(Q,i);//输出队列第一个元素for ( p = FirstNeghbor(G,i); p >0; p=NextNeighbor(G,i,w)){if (!visited[p]) {visit(p);visited[p] = true;EnQueue(Q, p);}}}}

 广度优先遍历过程

从顶点1出发:12563748

从顶点3出发:34678215

性能分析

邻接表和邻接矩阵空间复杂度

邻接表时间复杂度

邻接矩阵的时间复杂度

广度优先生成树

在广度遍历中可以得到一颗遍历树,为广度优先生成树

邻接矩阵唯一,生成树唯一

邻接表不唯一,生成树不唯一

6.3.2深度优先搜索

belike树的先序遍历

代码实现

#include<stdio.h>
#define maxnum 15
bool visited[maxnum];//定义辅助数组
void DFSTraverse(Graph G) {for (int i = 0; i < G.vexnum; i++){visited[i] = false;}//初始化数组for (int i = 0; i < G.vexnum; i++)//从0号顶点开始遍历{if (!visited[i]) {DFS(G, i);//深度优先遍历}}
}
void DFS(Graph G, int i) {visit(i);//访问visited[i] = true;//改为tfor (p = FirstNeghbor(G, i); p > 0; p = NextNeighbor(G, i, w)){if (!visited[p]) {DFS(G, p);}
}

深度优先遍历过程

从2出发:21563478

从3出发:34762158

性能分析

深度优先生成树和生成森林

非连通图可通过深度优先产生n棵生产树

6.3.3图的遍历与图的连通性

to无向图:调用DFS/BFS的次数=连通分量数

to有向图:强连通分量只调用一次DFS/BFS;

若从起始节点到其他节点都有路径,则只需调用一次

相关文章:

6.3图的遍历

图的遍历是指从某点出发,按照某种搜索方式沿着边访问图中所有节点 图的遍历算法主要有两种:广度优先,深度优先 都需要辅助数组visited[]来记录节点是否被访问过 6.3.1广度优先搜索 like层次遍历,需要辅助队列 代码实现 #include<stdio.h> #define maxnum 15 bool vi…...

2024数学建模国赛选题建议+团队助攻资料(已更新完毕)

目录 一、题目特点和选题建议 二、模型选择 1、评价模型 2、预测模型 3、分类模型 4、优化模型 5、统计分析模型 三、white学长团队助攻资料 1、助攻代码 2、成品论文PDF版 3、成品论文word版 9月5日晚18&#xff1a;00就要公布题目了&#xff0c;根据历年竞赛题目…...

大学课程-人机交互期末复习

绪论 什么是人机交互技术&#xff1f;⭐⭐ 是指关于设计、评价和实现供人们使用的交互式计算机系统&#xff0c;并围绕相关的主要现象进行研究的学。狭 义的讲&#xff0c;人机交互技术主要是研究人与计算机之间的信息交换&#xff0c;它主要包括人到计算机和计算机到人的 信息…...

畅游5G高速网络:联发科集成Wi-Fi6E与蓝牙5.2的系统级单芯片MT7922

这周末,除非外面下钞票,否则谁也拦不住我玩《黑神话悟空》(附:两款可以玩转悟空的显卡推荐) IPBrain平台君 集成电路大数据平台 2024年09月03日 17:28 北京 联发科一直以创新技术追赶市场需求…… “不努力向前游就会被海浪拍回岸边…” 芯片设计公司产品层出不穷,想要站…...

SpringSecurity原理解析(一)

一、SpringSecurity 核心组件 在SpringSecurity中的jar包有4个&#xff0c;作用分别为&#xff1a; spring-security-coreSpringSecurity的核心jar包&#xff0c;认证和授权的核心代码都在这里面spring-security-config如果使用Spring Security XML名称空间进行配置或Spring S…...

在Ubuntu 20.04上安装Nginx的方法

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。 简介 Nginx 是世界上最流行的 Web 服务器之一&#xff0c;负责托管互联网上一些最大和流量最高的网站。它是一个轻量级选择&#xff0c…...

基于苹果Vision Pro的AI NeRF方案:MetalSplatter

随着苹果Vision Pro的发布,混合现实(Mixed Reality, MR)技术迎来了一个新的发展阶段。为了充分利用Vision Pro的潜力,一款名为MetalSplatter的Swift/Metal库应运而生,它允许开发者在Vision Pro上以全立体的方式体验捕捉内容。本文将详细介绍MetalSplatter的特点及其如何为…...

linux系统中,计算两个文件的相对路径

realpath --relative-to/home/itheima/smartnic/smartinc/blocks/ruby/seanet_diamond/tb/parser/test_parser_top /home/itheima/smartnic/smartinc/corundum/fpga/lib/eth/lib/axis/rtl/axis_fifo.v 检验方式就是直接在当前路径下&#xff0c;把输出的路径复制一份&#xff0…...

[数据集][目标检测]抽烟检测数据集VOC+YOLO格式22559张2类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;22559 标注数量(xml文件个数)&#xff1a;22559 标注数量(txt文件个数)&#xff1a;22559 标…...

C和指针:结构体(struct)和联合(union)

结构体和联合 结构体 结构体包含一些数据成员&#xff0c;每个成员可能具有不同的类型。 数组的元素长度相同&#xff0c;可以通过下标访问(转换为指针)。但是结构体的成员可能长度不同&#xff0c;所以不能用下标来访问它们。成员有自己的名字&#xff0c;可以通过名字访问…...

[数据集][目标检测]电动车头盔佩戴检测数据集VOC+YOLO格式4235张5类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;4235 标注数量(xml文件个数)&#xff1a;4235 标注数量(txt文件个数)&#xff1a;4235 标注…...

软件工程知识点总结(2):需求分析(一)——用例建模

1 软件项目开发流程&#xff1a; 需求分析→概要设计→详细设计→编码实施→测试→产品提 交→维护 2 系统必须做什么&#xff1f; 获取用户需求&#xff0c;从用户角度考虑&#xff0c;用户需要系统必须完成哪些工作&#xff0c;也就是对目 标系统提出完整、准确、清晰、具体…...

2024 年高教社杯全国大学生数学建模竞赛C题—农作物的种植策略(讲解+代码+成品论文助攻,均已更新完毕)

2024数学建模国赛选题建议团队助攻资料-CSDN博客文章浏览阅读1k次&#xff0c;点赞20次&#xff0c;收藏24次。通过分析5个题目的特点&#xff0c;可知数学建模常用的模型大概可以分为五大类——https://blog.csdn.net/qq_41489047/article/details/141925859 本次国赛white学长…...

?.操作符是什么

?.操作符在不同的编程语言和上下文中可能有不同的含义和用途&#xff0c;但一般来说&#xff0c;它并不是一个广泛存在于所有编程语言中的标准操作符。不过&#xff0c;基于一些编程语言的特性和习惯&#xff0c;我们可以对?.操作符进行一些推测和解释。 1. 可选链操作符&am…...

ArcGIS出图格网小数位数设置

1、比如要去掉格网后面的小数点&#xff0c;如何设置呢&#xff1f; 2、如下图设置。...

数学建模_缺失值处理_拉格朗日、牛顿插值(全)

- 缺失值处理 1. 识别缺失值 在处理缺失值之前&#xff0c;首先需要识别数据中的缺失值。 1.1 使用 isna() 和 isnull() Pandas 提供了 isna() 和 isnull() 方法来检测缺失值&#xff0c;二者功能相同。 import pandas as pddf pd.DataFrame({A: [1, 2, None, 4],B: [None, 2,…...

算法题之水壶问题

水壶问题 有两个水壶&#xff0c;容量分别为 x 和 y 升。水的供应是无限的。确定是否有可能使用这两个壶准确得到 target 升。 你可以&#xff1a; 装满任意一个水壶清空任意一个水壶将水从一个水壶倒入另一个水壶&#xff0c;直到接水壶已满&#xff0c;或倒水壶已空。 示…...

Java项目: 基于SpringBoot+mysql蜗牛兼职网兼职平台管理系统(含源码+数据库+答辩PPT+毕业论文)

一、项目简介 本项目是一套基于SpringBootmysql蜗牛兼职网兼职平台管理系统 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操…...

C#数组中的Rank,GetUpperBound(), GetLength()

Rank-数组的秩&#xff0c;一维数组的Rank1&#xff1b;二维数组的Rank2&#xff1b; GetUpperBound()--获取每一维的索引的上限&#xff0c; 比如int[4,5], 那么GetUpperBound(0) 3; GetUpperBound(1) 4 ; 所以 对于二维数组来说 GetUpperBound(0)1行数&#xff1b; G…...

Android应用开发项目式教程——序

文章目录 Android技术本书特点本书内容本书参考 Android技术 Android是重要的客户端技术&#xff0c;因其开源开放的特点&#xff0c;Android在其初期就迅速成长为智能手机的主流操作系统&#xff0c;近年来更进一步成为智能电视、智能车载终端等智能设备的主流操作系统&#…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...