图的遍历介绍

概念

特点

无论是进行哪种遍历,均需要通过设置辅助数组标记顶点是否被访问来避免重复访问!!!!

类型

深度优先遍历

可以实现一次遍历访问一个连通图中的所有顶点,只要连通就能继续向下访问。

因此,深度递归次数就是图中连通分量数。

遍历过程

类似树的先根遍历,先访问结点,再访问与其邻接的第一个结点。

示例

遍历邻接矩阵表示图的实现

效率分析

非连通图的遍历

广度优先搜索

遍历过程

类似于树的层序遍历,先访问结点,再访问与结点邻接的所有结点。

 

非连通图的遍历

遍历邻接表表示图的实现

效率分析

DFS其底层是借助一个递归工作栈实现的。

而BFS是借助一个辅助队列实现的。

时间复杂度只与存储结构有关!!!!!

代码整合

#include <iostream> 
#define maxn 100
#define infi 333333
using namespace std;
int visit[maxn]={0}; 
//邻接矩阵:顶点数+边数+顶点表(一维)+边表(二维) 
typedef struct node{int vnum,arcnum;char vexs[maxn];int acr[maxn][maxn];
}adjgraph;
//邻接表:顶点数+边数+顶点表==>顶点类型:顶点信息+第一条边==> 边类型:顶点编号+权值+下一条边 
typedef struct acrnode{int num;int weigh;acrnode *nextacr;
}acrnode;
typedef struct vexnode{char vex;acrnode *firstacr;
}vexnode; 
typedef struct node{int vnum,acrnum;vexnode vexs[maxn];
}listgraph;//深度遍历 
//递归实现:传入图与起点,不断调用自身 
//用邻接矩阵实现 
void dfs1(adjgraph g,int v){ cout<<v<<endl;visit[v]=1;for(int i=0;i<g.vnum;i++){if(visit[i]==0&&acr[v][i]!=infi)dfs(g,i);}
}
//用邻接表实现 
void dfs2(listgraph l,int v){acrnode edge;vexnode vex; cout<<v<<endl;visit[v]=1;for(edge=l.vexs[v].firstacr;edge;edge=edge.nextacr){//遍历与v相连的所有边-有边 vex=l.vexs;//记录结点if(!visit[vex]) //且未被访问 dfs(l,vex);//访问结点 }
}//非递归实现:通过栈实现
//1.初始栈和标志数组
//2.起点元素入栈,
//3.栈非空:出栈访问,遍历下一条邻接边,未被访问时入栈,取下一个邻接结点 
stack<int> s
void dfs(adjgraph g,int v){//邻接矩阵实现 int t;initstack(s);push(s,v);while(!empty(s)){t=pop(s,v);if(!visit[t]){cout<<t<<endl;visit[t]=1;}for(int i=0;i<g.vnum;i++){if(g.arcnum[v][i]!=infi&&(!visit[i])){push(s,i);}}}
}//广度遍历
1.初始队列与标记数组
2.起点元素入队,
3.队非空:出队,遍历边,未被访问时访问入队 
void bfs(listgraph l,int v) {//用队列实现acrnode w;cout<<v<<endl;visit[v]=1;init(q); enqueue(q,v);while(!isempty(q)) {dequeue(q,v);for(w=l.vexs[v].firstacr;w;w=w.nextacr)//遍历邻接的所有边 {if(!visit[w]){cout<<w<<endl;visit[w]=1;enqueue(q,w);}}}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

算法专题总结链接地址

刷力扣的时候会遇到一些总结类型的题解&#xff0c;在此记录&#xff0c;方便自己以后找 前缀和 前缀和https://leetcode.cn/problems/unique-substrings-in-wraparound-string/solutions/432752/xi-fa-dai-ni-xue-suan-fa-yi-ci-gao-ding-qian-zhui-/ 单调栈 单调栈https:…

JVM (四)GC过程

一。概述 程序计数器、虚拟机栈、本地方法栈都是随线程生灭&#xff0c;栈帧随着方法的进入和退出做入栈和出栈操作&#xff0c;实现了自动的内存清理&#xff0c;因此&#xff0c;内存垃圾回收主要集中于Java堆和方法区中。 GC整体流程示意图&#xff1a; ① 年轻代对象的移动…

Codeforces Global Round 26 D. “a“ String Problem 【Z函数】

D. “a” String Problem 题意 给定一个字符串 s s s&#xff0c;要求把 s s s 拆分成若干段&#xff0c;满足以下要求&#xff1a; 拆分出来的每一个子段&#xff0c;要么是子串 t t t&#xff0c;要么是字符 a a a子串 t t t 至少出现一次 t ≠ " a " t \ne…

简单脉冲动画效果实现

简单脉冲动画效果实现 效果展示 CSS 知识点 CSS 变量的灵活使用CSS 动画使用 页面整体结构实现 <div class"pulse"><span style"--i: 1"></span><span style"--i: 2"></span><span style"--i: 3"…

html+CSS+js部分基础运用18

1. 按键修饰符的应用。①姓名&#xff1a;按下回车键时调用方法输出“姓名-密码”&#xff1b;②密码&#xff1a;按下shift回车时调用方法输出“姓名密码” 图1 初始效果图 图2 按键修饰符效果图 2. 仿淘宝Tab栏切换&#xff0c;熟悉…

图解Mamba——从流体力学的角度理解Mamba

1.Transformer的问题 上面是Transformer的网络结构。对于一句话的每个单词&#xff0c;都需要跟所有单词算注意力机制。因此注意力机制的计算复杂度为 O ( n 2 ) O(n^2) O(n2)&#xff0c;其中 n n n为句子的长度&#xff0c;即单词(符号)的个数。如下图所示。 所以这也是现在…

2021 hnust 湖科大 操作系统课设 报告+原代码+指导书+流程图源文件

2021 hnust 湖科大 操作系统课设 报告原代码指导书流程图源文件 详情 目录 验证类实验&#xff1a; 1 实验一&#xff1a;Windows进程管理 1 一、 实验题目&#xff1a; 1 二、 实验目的 1 三、 实验内容 1 四、 实验结果与分析 2 五、 小结与心得体会 5 实验二&#xff1a;L…

【HarmonyOS】遇见的问题汇总

一、当前编辑的页面&#xff0c;预览打不开 1、问题说明 当前编辑的页面&#xff0c;预览打不开&#xff0c;日志提示如下&#xff1a; Route information is not configured for the current page. To avoid possible redirection issues, configure route information for…

数据结构 —— 堆

1.堆的概念及结构 堆是一种特殊的树形数据结构&#xff0c;称为“二叉堆”&#xff08;binary heap&#xff09; 看它的名字也可以看出堆与二叉树有关系&#xff1a;其实堆就是一种特殊的二叉树 堆的性质&#xff1a; 堆中某个结点的值总是不大于或不小于其父结点的值&…

Vuepress 2从0-1保姆级进阶教程——标准化流程(Tailwindcss+autoprefixer+commitizen)

Vuepress 2 专栏目录【已完结】 1. 入门阶段 Vuepress 2从0-1保姆级入门教程——环境配置篇Vuepress 2从0-1保姆级入门教程——安装流程篇Vuepress 2从0-1保姆级入门教程——文档配置篇Vuepress 2从0-1保姆级入门教程——主题与部署 2.进阶阶段 Vuepress 2从0-1保姆级进阶教程—…

AM273X毫米波演示

介绍 毫米波演示展示了 AM273X SOC 使用毫米波 SDK&#xff08;软件开发工具包&#xff09;中的驱动程序的一些功能。它允许用户指定chirp配置文件并实时显示检测到的对象和其他信息。 以下是此演示功能的高级描述&#xff1a; 能够通过 UART 端口上的命令行界面 &#xff08;…

文字悬停效果

文字悬停效果 效果展示 CSS 知识点 CSS 变量使用回顾-webkit-text-stroke 属性的运用与回顾 页面整体结构实现 <ul><li style"--clr: #e6444f"><a href"#" class"text">First</a></li><li style"--cl…

苹果WWDC重磅发布的IOS 18、Apple Intelligence背后的技术分析!

2024年6月10日&#xff0c;在2024年WWDC全球开发者大会上&#xff0c;苹果推出了Apple Intelligence&#xff0c;这是深度集成到iOS 18、iPadOS 18和macOS Sequoia中的个人智能系统。 为了让大模型能在 iPhone 端侧跑&#xff0c;苹果还是做了很多事情的。接下来就跟大家介绍一…

Spring学习笔记

1 spring介绍 1)为什么学习spring ​ 1. Spring技术是JavaEE开发必备技能&#xff0c;企业开发技术选型命中率>90% ​ 2. 简化开发&#xff0c;降低企业级开发的复杂性 ​ 3. 框架整合&#xff0c;高效整合其他技术&#xff0c;提高企业级应用开发与运行效率 ​ 作为一…

IDEA创建Mybatis项目

IDEA创建Mybatis项目 第一步&#xff1a;创建库表 -- 创建数据库 create database mybatis_db;-- 使用数据库 use mybatis_db;-- 创建user表 CREATE TABLE user (id INT AUTO_INCREMENT PRIMARY KEY,username VARCHAR(50) NOT NULL,password VARCHAR(50) NOT NULL,email VARC…

Django API开发实战:前后端分离、Restful风格与DRF序列化器详解

系列文章目录 Django入门全攻略&#xff1a;从零搭建你的第一个Web项目Django ORM入门指南&#xff1a;从概念到实践&#xff0c;掌握模型创建、迁移与视图操作Django ORM实战&#xff1a;模型字段与元选项配置&#xff0c;以及链式过滤与QF查询详解Django ORM深度游&#xff…

第十五届蓝桥杯大赛 国赛 pb组F题【括号与字母】(15分) 栈的应用

博客主页&#xff1a;誓则盟约系列专栏&#xff1a;IT竞赛 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ 试题F:括号与字母 【问题描述】 给定一个仅包含小写字母和括号的字符串 S …

【CentOS 7】挑战探索:在CentOS 7上实现Python 3.9的完美部署指南

【CentOS 7】挑战探索&#xff1a;在CentOS 7上实现Python 3.9的完美部署指南 大家好 我是寸铁&#x1f44a; 总结了一篇【CentOS 7】挑战探索&#xff1a;在CentOS 7上实现Python 3.9的完美部署指南详细步骤✨ 喜欢的小伙伴可以点点关注 &#x1f49d; 前言 此篇教程只适用于p…

LeetCode 算法: 旋转图像c++

原题链接&#x1f517;&#xff1a; 旋转图像 难度&#xff1a;中等⭐️⭐️ 题目 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图…

OrangePi AIpro小试牛刀-目标检测(YoloV5s)

非常高兴参加本次香橙派AI Pro&#xff0c;香橙派联合华为昇腾打造的一款AI推理开发板评测活动&#xff0c;以前使用树莓派Raspberry Pi4B 8G版本&#xff0c;这次有幸使用国产嵌入式开发板。 一窥芳容 这款开发板搭载的芯片是和华为昇腾的Atlas 200I DK A2同款的处理器&#…