程序员经验分享-hwhale

数据结构 图 part2

2023-11-12

图的遍历

在这里插入图片描述

深度优先遍历（DFS)

遍历步骤

①在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w;

②从w1出发，访问与w1邻接但还未被访问过的顶点w2;然后再从w2出发，进行类似的访问…

③如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。

④接着，退到前一次刚访问过的顶点,看是否还有其它未被访问的邻接顶点。

如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问;

如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

在这里插入图片描述

注意:在邻接表中，并非每个链表元素(表结点)都被扫描到,稀疏图时遍历速度较快。

邻接矩阵的存储

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未访问，递归调用
}

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。

稠密图适于在邻接矩阵上进行深度遍历

邻接表的存储

void DFS(ALGraph G, int v){//图G为邻接表类型
    cout<<v; 
    visited[v]=true;//访问第v个顶点
p= G.vertices[v].firstarc; //p指向v的边链表的第一个边
    while(p!=NULL){//边结点非空
        w=p->adjvex;//表示w是v的邻接点
        if(!visited[w]) DFS(G, w);//如果w未访问，则递归调用
        p=p->nextarc;//p指向下一个边结点
    }}

用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。

稀疏图适于在邻接表上进行深度遍历

广度优先遍历（BFS)

遍历步骤

①在访问了起始点v之后，依次访问v的邻接点;

②然后再依次访问这些顶点中未被访问过的邻接点;直到所有顶点都被访问过为止。

在这里插入图片描述

在这里插入图片描述

用邻接矩阵来表示图，对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行( n个元素)，时间复杂度为O(n2)。

稠密图适于在邻接矩阵上进行广度遍历

用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。

稀疏图适于在邻接表上进行广度遍历

非连通图的遍历

连通分量

当无向图为非连通图时，从图中某一顶点出发，利用BFS算法或DFS搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在最大连通子图(连通分量)的所有顶点。
非连通无向图的最大连通子图

在这里插入图片描述

如何遍历

从每个连通分量中选择初始点，分别进行遍历，才能够访问到图中的所有顶点。

生成树

该连通图的一个极小连通子图

含有n个顶点,但只有构成一棵树的*(n-1)*条边;

使用不同的遍历方法，可以得到不同的生成树;

从不同的顶点出发，也可能得到不同的生成树;

在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

深度优先

图论

数据结构 图 part2 的相关文章

  • Vue基础知识（Web开发技术）（四）—路由

    这章非常重要哈 编程编程编程 随缘上代码 导读 本章重点 了解vue router的实现原理 熟练路由的安装与使用 掌握路由对象的常用属性和动态路由的匹配及路由嵌套的方法 掌握命名路由 命名视图和编程式导航及query params传参方式

  • VSCode无法在终端使用`conda activate`命令来更换python环境解决方法

    VSCode无法在终端使用conda activate命令来更换python环境 现象 在终端输入conda activate命令后出现如下图所示的报错 原因 powershell默认没有打开脚本加载功能 无法加载conda init 解决

  • 无线传感网络

    第一 二章 无线传感网络的定义 无线传感网络是大量的静止节点或移动的传感器以自组织和多跳的方式构成的无线网络 目的是协作地探测 处理和传输网络覆盖区域内感知对象的监测信息 并报告给用户 传感器节点的组成 数据处理 数据采集模块 传感器 A

  • 最好的网页浏览器_谷歌浏览器双击关闭标签的步骤_如何使Chrome能够双击关闭标签页...

    我们在使用浏览器浏览网页的时候 经常会打开多个书签 很多浏览器都支持双击标签页就可以直接关闭 但是有不少用户使用谷歌浏览器chrome却发现无法直接双击关闭标签页 那么如何使Chrome能够双击关闭标签页呢 我们需要借助扩展程序 现在随小编

随机推荐

  • 最短路径——迪杰斯特拉（Dijkstra）算法

    如果你要从一个城市到另一个城市 中途可以有很多种换乘方法 根据不同人的需求 怎么样才能实现价格最少 价格和路程成正比 怎么样能实现换乘次数最少 有很多种可能的情况 这时候怎么样找到合适的方案呢 这就需要研究图的最短路径问题 不过在网图和非网

  • 12、【创业必备企业架构，可开发任意项目】SpringCloud大型企业分布式微服务云架构源码之MySQL 排序

    MySQL 排序 我们知道从 MySQL 表中使用 SQL SELECT 语句来读取数据 如果我们需要对读取的数据进行排序 我们就可以使用 MySQL 的 ORDER BY 子句来设定你想按哪个字段哪种方式来进行排序 再返回搜索结果 语法

  • Shell-打印文件空行行号

    1 写一个 bash脚本以输出一个文本文件 nowcoder txt中空行的行号 可能连续 从1开始 awk s print NR nowcoder txt 2 去掉文件的空行输出 方法1 awk if 0 print 0 nowcoder

  • 【Python 3.7】河流：创建一个字典，在其中存储三条大河流及其流经的国家。其中一个键 — 值对可能是 'nile': 'egypt' 。

    Python 3 7 河流 创建一个字典 在其中存储三条大河流及其流经的国家 其中一个键 值对可能是 nile egypt 题目 河流 创建一个字典 在其中存储三条大河流及其流经的国家 其中一个键 值对可能是 nile egypt 使用循环

  • acwing算法基础课笔记7

    时间复杂度分析

  • easyui toolbar工具div form放外面表单无法清空重置

    form 一定要放在div内部才行 这也是我自己踩过的坑

  • Unity中的资源管理-使用Profile分析内存使用情况

    本文分享Unity中的资源管理 使用Profile分析内存使用情况 在上一篇文章中 我们介绍了Ab的加载和使用 并简单列举了其内存分布情况 今天我们继续探索Ab的内存 观察和实验其在各种阶段的分布情况 Profile性能分析工具 在一切开始

  • 掌握Python的X篇_17_循环语句(while；for var in ；range)

    文章目录 1 为什么需要循环 2 while循环 3 for in循环 4 range函数 1 为什么需要循环 循环语句方便我们做重复的事情 比如 for i in range 0 3 print 重要的事情说三遍 运行效果如下 Pytho

  • C++ 中内存分区总结

    背景 C 中最基本的存储单位是字节 C 中所有的数据都是由对象组成的 每一个对象都包含了一个或多个内存位置 C 中有多种不同类型的内存区域 不同区域存放不同的数据 赋予数据不同的生命周期 程序在执行时将供用户使用内存大致划分为以下区域 常量

  • 激光灯

    激光等中使用的通讯方式 简介 通讯介绍 DMX512通讯 DMX512通讯物理层 DMX512通讯应用层 ILDA通讯 ILDA通讯物理层 DMX512通讯应用层 Art Net 网络通讯 简介 本文作为起始书写的第一篇 但可能不是专栏中的

  • Error : Program type already present: android.support.design.widget.CoordinatorLayout$

    Error Program type already present android support design widget CoordinatorLayout 原因是在页面中使用recyclerView导致的 主要是design和co

  • Cache-Control max-age=0

    http blog csdn net ysdaniel article details 7969766 Cache Control no cache 强制每次请求直接发送给源服务器 而不经过本地缓存版本的校验 这对于需要确认认证应用很有用

  • 第二章 下载AOSP WiFi相关的代码

    第一章 国内下载AOSP最新源码的方法 文章目录 前言 一 需下载的仓库清单 二 下载命令 三 代码仓目录结构 总结 前言 WiFi相关的仓库包括Settings SettingsLib wifi service wpa supplican

  • micropython移植教程_Micropython移植篇——从点亮一个灯开始

    收到论坛申请的 MicroPython入门指南 已经两天了 看到了第四章 没有再往下看了 感觉应该先找个硬件移植 然后再往下看 跟着学习 这样才有意义 好了 先说下移植的过程吧 硬件采用的是STM32F429DISC 具体步骤 第一步 下载

  • Matlab 学习笔记 （部分内容系转载）

    由于要参加数学建模比赛的原因 我需要在不到一周的时间内初步地学习Matlab 因此 我希望把我在学习过程中阅读的资料记录下来 方便跟我一样需要在较短时间内速成Matlab的同学 基本上我记录的东西都是从网上的资料总结而来 所以这篇文章更偏向

  • MySQL读写分离实战

    1 MySQL读写分离概念 MYSQL读写分离的原理其实就是让Master数据库处理事务性增加 删除 修改 更新操作 create insert update delete 而让Slave数据库处理查询 select 操作 MySQL读写分

  • Java基础--------集合框架

    参考http blog csdn net zhongkelee article details 46801449 点击打开链接 以此为模板 自己做了整理 修改 目录 一 概念 二 集合框架的体系 2 1 Collection接口 2 1 1

  • 三维人脸重建（二）——Python生成ply文件

    目录 引言 一 ply格式模型介绍 二 代码 注 引言 本文主要以做坐标点为例 我们知道python对数据的处理主要是以numpy的形式 一般三维空间坐标的矩阵在python中为 x1 y1 z1 x2 y2 z2 xn yn zn 然后可

  • Java中的栈区和堆区问题（关于数组）

    Java中创建的局部变量等是存放在栈区的 而数组是存放在堆区的 那些new出来的对象也大多存放于堆区 栈区的空间往往不大 而堆区空间就会大很多 这里我们创建一个数组 如果在idea中打印a 会得到一串符号 这个是数组在堆区首元素的地址 代表

  • 数据结构 图 part2

    文章目录 图的遍历 深度优先遍历 DFS 遍历步骤 邻接矩阵的存储 邻接表的存储 广度优先遍历 BFS 遍历步骤 非连通图的遍历 连通分量 如何遍历 生成树 图的遍历 深度优先遍历 DFS 遍历步骤 在访问图中某一起始顶点v后 由v出发 访

热门标签