【数据结构】六、图:4.图的遍历(深度优先算法DFS、广度优先算法BFS)

三、基本操作

文章目录

  • 三、基本操作
    • 1.图的遍历
      • 1.1 深度优先遍历DFS
        • 1.1.1 DFS算法
        • 1.1.2 DFS算法的性能分析
        • 1.1.3 深度优先的生成树和生成森林
      • 1.2 广度优先遍历BFS
        • 1.2.1 BFS算法
        • 1.2.2 BFS算法性能分析
        • 1.2.3 广度优先的生成树和生成森林
      • 1.3 图的遍历与图的连通性

1.图的遍历

图的遍历是和树的遍历类似,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次, 这一过程就叫做图的遍历(Traversing Graph)。

对于图的遍历来,通常有两种遍历次序方案:

  1. 深度优先遍历
  2. 广度优先遍历

1.1 深度优先遍历DFS

深度优先遍历(Depth First Search),也有称为深度优先搜索,简称为DFS。

1.1.1 DFS算法

深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样,这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图,每次都尝试向更深的节点走。它的基本思想如下:

首先访问图中某一起始顶点v,然后由v出发,访问与v邻接且未被访问的任一顶点w1,再访问与 w1 邻接且未被访问的任一顶点…重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直至图中所有顶点均被访问过为止。

在这里插入图片描述

先序遍历:12563478

DFS 最显著的特征在于其 递归调用自身。同时与 BFS 类似,DFS 会对其访问过的点打上访问标记,在遍历图时跳过已打过标记的点,以确保 每个点仅访问一次。符合以上两条规则的函数,便是广义上的 DFS。算法过程如下:

bool visited[MAX_VERTEX_NUM];	//访问标记数组//从顶点出发,深度优先遍历图G
void DFS(Graph G, int v){visit(v);	//访问顶点visited[v] = TRUE;	//设已访问标记//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点,若有则返回顶点号,否则返回-1。//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点,返回除w外顶点vfor(int w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){if(!visited[w]){	//w为v的尚未访问的邻接顶点DFS(G, w);//递归}}
}

但是如果是非连通图,那么就不能从一个结点遍历所有的结点。这个时候需要添加一个函数来寻找没被访问的结点。

//深度遍历算法final
bool visited[MAX_VERTEX_NUM];	//访问标记数组//从顶点出发,深度优先遍历图G
void DFS(Graph G, int v){visit(v);	//访问顶点visited[v] = TRUE;	//设已访问标记//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点,若有则返回顶点号,否则返回-1。//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点,返回除w外顶点vfor (int w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){if (!visited[w]){	//w为v的尚未访问的邻接顶点DFS(G, w);//递归}}
}//对图进行深度优先遍历
void DFSTraverse(MGraph G){for (int v=0; v<G.vexnum; v++){visited[v] = FALSE;	//初始化已访问标记数据}for (int v=0; v<G.vexnum; v++){	//从v=0开始遍历if(!visited[v]){DFS(G, v);}}
}
1.1.2 DFS算法的性能分析

空间复杂度:DFS算法是一个递归算法,需要借助一个递归工作栈。最坏情况是 O(|V|)

在这里插入图片描述

时间复杂度:

  • 邻接矩阵:需要访问|V|个结点,然后查找|V|个结点的邻接点|V|个,那么时间复杂度为 O(|V|+|V|2)。
    O(|V|2)
  • 邻接表:需要访问|V|个结点,然后查找每个结点的邻接点总共需要O(2|E|)时间,那么时间复杂度为 O(|V|+2|E|)。
    O(|V|+|E|)
1.1.3 深度优先的生成树和生成森林

对一个图进行所有结点的遍历,那么在这个遍历过程中不是所有的边都被用到:

在这里插入图片描述

**【注意】**1. 从不同的点出发,得到的遍历序列不一样;即使从同一个点出发,也可能得到不同的遍历序列。

  1. 因为邻接矩阵的表示方式是唯一的,所以DFS算法得到的遍历序列是唯一的。但是因为单链表的表示方式不是唯一的,所以DFS算法得到的遍历序列不是唯一的。

当图里面有多个连通分量,那么就会有多个生成树,这时候这些树就组成一个生成森林。

在这里插入图片描述

1.2 广度优先遍历BFS

广度优先遍历(Breadth First Search),又称为广度优先搜索,简称BFS。

1.2.1 BFS算法

如果说图的深度优先遍历类似树的前序遍历,那么图的广度优先遍历就类似于树的层序遍历了。

广度优先搜索是一种分层的查找过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况,因此它不是一个递归的算法。为了实现逐层的访问,算法必须借助一个辅助队列,以记忆正在访问的顶点的下一层顶点。

在这里插入图片描述

以下是广度优先遍历的代码:

从结点v出发遍历:

//邻接矩阵的广度遍历算法。从结点v出发遍历
void BFS(MGraph G, int v){Queue Q;//把所有结点全部标记为false,表示没有访问过for(int i = 0; i<G.numVertexes; i++){visited[i] = FALSE;}InitQueue(&Q);	//初始化一辅助用的队列visit(v);	//访问顶点vivited[v] = TRUE;	//设置当前访问过EnQueue(&Q, v);	//将此顶点入队列//若当前队列不为空while(!QueueEmpty(Q)){DeQueue(&Q, &v);	//顶点v出队列//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点,若有则返回顶点号,否则返回-1。//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点,返回除w外顶点v//把出队结点的相邻的所有结点入队for(int w=FirstNeighbor(G, v); w>=0; w=NextNeighbor(G, v, w)){//检验v的所有邻接点if(!visited[w]){visit(w);	//访问顶点wvisited[w] = TRUE;	//访问标记EnQueue(&Q, w);	//顶点w入队列}//if}//for}//while
}

但是如果是非连通图,那么就不能从一个结点遍历所有的结点。这个时候需要添加一个函数来寻找没被访问的结点。

//邻接矩阵的广度遍历算法final
void BFSTraverse(MGraph G){int i, j;Queue Q;//把所有结点全部标记为false,表示没有访问过for(i = 0; i<G.numVertexes; i++){visited[i] = FALSE;}InitQueue(&Q);	//初始化一辅助用的队列for(i=0; i<G.numVertexes; i++){		//这里是从0开始//若是未访问过就处理if(!visited[i]){//下面的部分相当于前面写的BFS(G, v);visit(i);	//访问顶点vivited[i] = TRUE;	//设置当前访问过EnQueue(&Q, i);	//将此顶点入队列//若当前队列不为空while(!QueueEmpty(Q)){DeQueue(&Q, &i);	//顶点i出队列//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点,若有则返回顶点号,否则返回-1。//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点,返回除w外顶点v//把出队结点的相邻的所有结点入队for(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){//检验v的所有邻接点if(!visited[j]){visit(j);	//访问顶点jvisited[j] = TRUE;	//访问标记EnQueue(Q, j);	//顶点j入队列}//if}//for}//while}//if}//for
}

下面的部分相当于前面写的BFS(G, v);,所以还有一种写法是把BFSTraverse 和 BFS分开

//对非连通图的广度遍历算法final
void BFSTraverse(MGraph G){Queue Q;InitQueue(&Q);	//初始化一辅助用的队列int i;//把所有结点全部标记为false,表示没有访问过for(i=0; i<G.numVertexes; i++){visited[i] = FALSE;}for(i=0; i<G.numVertexes; i++){		//这里是从0开始//若是未访问过就处理if(!visited[i]){BFS(G, i);	//调用BFS函数}//if}//for
}void BFS(MGraph G, int v){visit(v);	//访问顶点vivited[v] = TRUE;	//设置当前访问过EnQueue(&Q, v);	//将此顶点入队列//若当前队列不为空while(!QueueEmpty(Q)){DeQueue(&Q, &v);	//顶点i出队列//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点,若有则返回顶点号,否则返回-1。//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点,返回除w外顶点v//把出队结点的相邻的所有结点入队for(w=FirstNeighbor(G, v); w>=0; w=NextNeighbor(G, v, w)){//检验v的所有邻接点if(!visited[w]){visit(w);	//访问顶点wvisited[w] = TRUE;	//访问标记EnQueue(Q, w);	//顶点w入队列}//if}//for}//while
}

对于无向图,调用BFS函数的次数 = 连通分量

1.2.2 BFS算法性能分析

空间复杂度:最坏情况是当所有结点都连在第一个结点上,辅助队列大小为 O(|V|)

时间复杂度:

  • 邻接矩阵:需要访问|V|个结点,然后查找|V|个结点的邻接点|V|个,那么时间复杂度为 O(|V|+|V|2)。
    O(|V|2)
  • 邻接表:需要访问|V|个结点,然后查找每个结点的邻接点总共需要O(2|E|)时间,那么时间复杂度为 O(|V|+2|E|)。
    O(|V|+|E|)
1.2.3 广度优先的生成树和生成森林

对一个图进行所有结点的遍历,那么在这个遍历过程中不是所有的边都被用到:

在这里插入图片描述

【注意】因为邻接矩阵的表示方式是唯一的,所以BFS算法得到的遍历序列是唯一的。但是因为单链表的表示方式不是唯一的,所以BFS算法得到的遍历序列不是唯一的。

在这里插入图片描述

当图里面有多个连通分量,那么就会有多个生成树,这时候这些树就组成一个生成森林。

1.3 图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性。

  • 对于无向图进行BFS/DFS遍历。

    调用BFS/DFS函数的次数 = 连通分量数。

    • 若是连通图的,则从任一结点出发, 仅需一次遍历就能够访问图中的所有顶点,只需调用1次BFS/DFS。
    • 若是非连通的,则从某一个顶点出发,一次遍历只能访问到该顶点所在连通分量的所有顶点,而对于图中其他连通分量的顶点,则无法通过这次遍历访问。
  • 对于有向图进行BFS/DFS遍历。
    调用BFS/DFS函数的次数要具体问题具体分析

    • 若起始顶点到其他各顶点都有路径,则只需调用1次BFS/DFS函数,对于强连通图,从任一结点出发都只需调用1次BFS/DFS。
    • 但是从起始顶点不能到达所有结点,那么需要调用多次BFS/DFS。

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

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

相关文章

Nginx系列-Nginx Location匹配规则

文章目录 Nginx系列-Nginx Location匹配规则1. 语法基础2. 匹配规则2.1 精确匹配&#xff08;&#xff09;2.2. 最长前缀匹配&#xff08;^~&#xff09;2.3. 正则表达式匹配&#xff08;~和~*&#xff09;2.4. 普通前缀匹配&#xff08;无修饰符&#xff09;2.5. 默认匹配&…

贷齐乐hpp+php特性注入

文章目录 运行过程waf第一层waf拦截第二层waf拦截 数据库查询语句注入思路注入 运行过程 foreach ($_REQUEST as $key > $value) {$_REQUEST[$key] dowith_sql($value);}$request_uri explode("?", $_SERVER[REQUEST_URI]);if (isset($request_uri[1])) {$rewr…

OpenGL3.3_C++_Windows(34)

demo 1 Fresnel-Schlick PBR直接光源 顾名思义&#xff1a;直接光源指有光源直接照射到点p 的辐射强度&#xff0c;由于一个光源只会有一个光线wi影响点p&#xff0c;所以和之前的计算没什么差异对于影响p的光源&#xff0c;并不需要积分计算半球形辐照度&#xff0c;遍历每个…

redis面试(十)锁释放

自动释放 首先锁的释放分为两种&#xff0c;一种是自动释放&#xff0c;加入说加锁的线程宕机了不在了&#xff0c;我们之前说过这个。 那这个线程中的对redis这个锁不断刷新过期时间的看门狗逻辑就没有了&#xff0c;所以这个锁最多等待30s的时间就会自动过期删除&#xff0c…

为什么选择在Facebook投放广告?

2024年了你还没对 Facebook 广告产生兴趣&#xff1f;那你可就亏大了&#xff01; 今天这篇文章&#xff0c;我们会分享它对你扩大业务的好处。要知道&#xff0c;Facebook 广告凭借它庞大的用户群和先进的定位选项&#xff0c;已经是企业主们有效接触目标受众的必备神器。接下…

【uniapp】uniapp+vue2微信小程序实现分享功能

uniappvue2做的微信小程序实现分享功能 问题描述 uniappvue2做的微信小程序&#xff0c;发布以后点击右上角三个点&#xff0c;分享小程序的时候&#xff0c;转发和分享按钮都是灰色 解决方案 转发、分享、复制链接这几个功能需要自己来手动写方法&#xff0c;考虑到每个页…

Unity入门3——脚本入门

本文使用的代码编辑器为VSCode 安装接口有&#xff1a; 通过将变量设置为public&#xff0c;可以直接在unity的Inspector面板中看到相关变量。此时可直接将需要的素材拖拽到变量处。 [SerializeField]可序列化&#xff1a;定义后可以使非公共的属性也显示在unity面板 [Range]…

搜维尔科技:【研究】大屏幕沉浸式系统的优势,视觉冲击强、‌分辨率高、‌画面层次感强以及沉浸式交互性体验好等!

大屏幕沉浸式系统的优势主要体现在视觉冲击强、‌分辨率高、‌画面层次感强以及沉浸式交互性体验好。‌ 视觉冲击强&#xff1a;‌大屏幕沉浸式系统通过使用多台投影机投射画面&#xff0c;‌结合高质量影片&#xff0c;‌营造出场景环境&#xff0c;‌通过视觉艺术直击体验者…

js 深入理解原型(prototype)及如何创建对象

目录 1. 概述2. 工厂模式3. 构造函数模式3.1 创建的格式3.2 JS内部执行步骤3.3 constructor 构造器3.4 构造函数也是函数3.5 构造函数的问题 4. 原型模式 prototype4.1 理解原型本质4.2 原型层级(访问一个属性&#xff0c;查询的次序&#xff09;4.2.1 查询次序&#xff1a;实例…

SeaTunnel 实战: Apache SeaTunnel 安装与部署

文章目录 一、准备工作1.1 环境1.2 下载 二、SeaTunnel安装2.1 解压安装包2.2.配置环境变量2.3.配置立刻生效2.4 下载SeaTunnel相关jar包2.5 测试验证2.6 启动服务 三、SeaTunnel Web 1.0.1安装3.1 将下载的压缩包解压缩到指定目录下3.2 设置 SeaTunnel Web 环境变量3.3 初始化…

pythonUI自动化008::allure测试报告(安装及应用)

allure报告预览 1 下载jdk&#xff0c;配置jdk Path变量&#xff1a; https://www.cnblogs.com/FBGG/p/15103119.html&#xff08;这里不作阐述&#xff0c;请看该偏文章配置即可&#xff09; 2 下载allure驱动&#xff0c;配置allure Path变量&#xff1a; 下载allure驱动&a…

【免费】最新区块链钱包和私钥的助记词碰撞器,bybit使用python开发

使用要求 1、用的是google里面的扩展打包成crx文件&#xff0c;所以在使用之前你需要确保自己电脑上有google浏览器&#xff0c;而且google浏览器版本需要在124之上。&#xff08;要注意一下&#xff0c;就是电脑只能有一个Chrome浏览器&#xff09; 2、在win10上用vscode开发…

锂电池剩余寿命预测 | Matlab基于Transformer-GRU的锂电池剩余寿命预测

目录 预测效果基本介绍程序设计参考资料 预测效果 基本介绍 Matlab基于Transformer-GRU的锂电池剩余寿命预测&#xff0c;Transformer结合门控循环单元。 Matlab基于Transformer-GRU的锂电池剩余寿命预测&#xff08;单变量&#xff09; 运行环境Matlab2023b及以上。 首先从…

C++初阶:模版进阶【非类型模版参数】【模版的特化】【模版分离编译】

目录 一.非类型模版参数 二.模版的特化 2.1模版特化的概念 2.2函数模版的特化 2.3类模版特化 2.3.1全特化 2.3.2偏特化 2.3.3使用类模版特化 三.模版分离编译 一.非类型模版参数 模板参数分类类型形参与非类型形参。 类型形参&#xff1a;出现在模板参数列表中&…

【数据结构算法经典题目刨析(c语言)】使用队列实现栈(图文详解)

目录 一.题目描述 二.解题思路 三.代码实现 &#x1f493; 博客主页&#xff1a;C-SDN花园GGbond ⏩ 文章专栏&#xff1a;数据结构经典题目刨析(c语言) 一.题目描述 二.解题思路 首先这道题需要我们使用两个队列来完成栈的实现, 这里我们的思路是, 栈的要求是后进先出, …

C语言进阶——一文带你深度了解“C语言关键字”(中篇6)

本篇文章记录我学习C语言进阶知识——C语言关键字&#xff0c;旨在记录分享&#xff0c;希望我的分享能带给你不一样的收获&#xff01; 目录 一、return关键字 二、const 关键字也许该被替换为 readolny &#xff08;一&#xff09;、 const 修饰的只读变量 &#xff08;二…

腾讯云COS和阿里云OSS在Springboot中的使用

引言&#xff1a;之前本来是用OSS做存储的&#xff0c;但是上线小程序发现OSS貌似消费比COS多一些&#xff0c;所以之前做了技术搬迁&#xff0c;最近想起&#xff0c;打算做个笔记记录一下&#xff0c;这里省去在阿里云注册OSS或腾讯云中注册COS应用了。 一、OSS 1、配置yml …

C ++ 也可以搭建Web?高性能的 C++ Web 开发框架 CPPCMS + MySQL 实现快速入门案例

什么是CPPCMS&#xff1f; CppCMS 是一个高性能的 C Web 开发框架&#xff0c;专为构建快速、动态的网页应用而设计&#xff0c;特别适合高并发和低延迟的场景。其设计理念类似于 Python 的 Django 或 Ruby on Rails&#xff0c;但针对 C 提供了更细粒度的控制和更高效的性能。…

Golang | Leetcode Golang题解之第330题按要求补齐数组

题目&#xff1a; 题解&#xff1a; func minPatches(nums []int, n int) (patches int) {for i, x : 0, 1; x < n; {if i < len(nums) && nums[i] < x {x nums[i]i} else {x * 2patches}}return }

【Python学习手册(第四版)】学习笔记19-函数的高级话题

个人总结难免疏漏&#xff0c;请多包涵。更多内容请查看原文。本文以及学习笔记系列仅用于个人学习、研究交流。 本文主要介绍函数相关的高级概念&#xff1a;递归函数、函数注解、lambda表达式函数&#xff0c;常用函数工具如map、filter、reduce&#xff0c;以及通用的函数设…