数据结构学习笔记——图的遍历算法(深度优先搜索和广度优先搜索)

简介: 数据结构学习笔记——图的遍历算法(深度优先搜索和广度优先搜索)

一、图的遍历概念


图的遍历指从图中某一顶点出发(任意一个顶点都可以作为访问的起始顶点),按照某种遍历方法,对图中所有的顶点访问一次且只访问一次。图与树不一样,其中一个顶点可能与多个顶点相连,所以需记录已访问过的顶点,当访问一个顶点后,考虑如何选取下一个要访问的顶点。


图的遍历分为两种,深度优先搜索和广度优先搜索,这两种方法对无向图和有向图都适用。


二、深度优先搜索(DFS)


(一)DFS算法步骤


前面文章中,讲到过二叉树的先序遍历,其实这里图的深度优先搜索(DFS)是由其推广而来的。


二叉树的先序遍历中,首先是根结点,遍历完根结点的左子树,然后再遍历完根结点的右子树,依次下去至所有结点都遍历到。


图的深度优先搜索首先选取图中某一顶点vi,访问后,任意选取一个与vi邻接的顶点,且该顶点未被访问,……,继续重复该过程,直到图中所有与vi连通的顶点都被访问到;若还有顶点未被访问到,则另外选取一个未被访问的顶点再次作为起始点,重复以上步骤,继续直至图中所有结点被访问。

可以看出DFS算法是一个递归过程,其中需借助一个栈完成操作。


写出下面这个图的深度优先遍历序列:

1667295617310.jpg


其深度优先遍历序列为:0,4,6,9,8,7,5,3,2,1。


1、邻接表DFS算法步骤


例如下面这个无向图:

1667295641716.jpg


该图的邻接表如下:

1667295652898.jpg

通过邻接表进行深度优先搜索的步骤如下(以V1为访问起始点,不唯一):

1、首先访问0,即V1,访问后标记已访问过;

2、查看V1单链表,第一个未访问的邻接顶点为2,即V3,并以V3为出发点继续深度遍历;

3、查看V3单链表,其第一个未访问的邻接顶点为6,即V7,再以V7为出发点继续深度遍历;

4、查看V7单链表,其邻接顶点为2,即V3,它已经被访问过,于是回到V3单链表,搜索下一个未被访问的邻接顶点;

5、查看V3单链表,其下一个未访问的邻接顶点为5,即V6,以V6为出发点继续深度遍历;

6、查看V6单链表,其邻接顶点为2,也是已经被访问过,于是回到V3单链表,搜索下一个未被访问的邻接顶点;

7、查看V3单链表,其邻接顶点为0,即V1,一开始被访问过,于是回到V1单链表,搜索下一个未被访问的邻接顶点;

8、查看V1单链表,其下一个未访问的邻接顶点为1,即V2,并以V2为出发点继续深度遍历;

9、查看V2单链表,其第一个未访问的邻接顶点为4,即V5,再以V5为出发点继续深度遍历;

10、查看V5单链表,其第一个未访问的邻接顶点为7,即V8,再以V8为出发点继续深度遍历;

11、查看V8单链表,其邻接顶点为4,即V5,已经被访问过,于是回到V5单链表,搜索下一个未被访问的邻接顶点;

12、查看V5单链表,其下一个未被访问的邻接顶点为1,即V2,于是回到V2单链表,搜索下一个未被访问的邻接顶点;

13、查看V2单链表,其邻接顶点为3,即V4,并以V4为出发点继续深度遍历;;

14、查看V4单链表,其邻接顶点为7,即V8,再以V8为出发点继续深度遍历;

15、查看V8单链表,其邻接顶点为3,即V4,再以V4为出发点继续深度遍历;

16、查看V4单链表,其邻接顶点为1,即V2,再以V2为出发点继续深度遍历;

17、查看V2单链表,其邻接顶点为0,即V1,再以V1为出发点继续深度遍历;

18、查看V1单链表,其邻接顶点为2,即V3,V3中已经不存在未访问的顶点,于是回到V1单链表。

19、查看V1单链表,下一个邻接顶点为1,即V2,V2中已经不存在未访问的顶点,最后回到V1单链表,遍历完成。

故该图的深度优先遍历序列为:V1、V3、V7、V6、V2、V5、V8、V4。


2、邻接矩阵DFS算法步骤


通过图的邻接矩阵实现深度优先搜索,例如下面这个图(以V1为访问起始点,是唯一的):


例如,对于下面这个有向图,对其进行深度优先搜索:

1667295683422.jpg


其邻接矩阵如下:

1667295695278.jpg

1、由V1开始,如下表【第一行为回退点,第二行为深度优先搜索得到的序列】:


V1



2、通过其邻接矩阵知,访问第一行第二列的1对应的V2顶点,由于它是在V1的行中被访问到的,所以回退点为V1:


V1
V1 V2



3、由于访问了V2,即开始访问V2行,访问第二行第三列的1对应的V4顶点,由于它是在V2的行中被访问到的,所以回退点为V2:


V1 V2
V1 V2 V4


4、由于访问了V4,即开始访问V4行,访问第四行第五列的1对应的V5顶点,由于它是在V4的行中被访问到的,所以回退点为V4:


V1
V2 V4
V1 V2 V4 V5


5、由于访问了V5,即开始访问V5行,由于第五行都为0,回退到V4,由于V4行顶点都访问完,回退到V2,由于V2行顶点都访问完,回退到V1行,此时V1行还剩第一行第三列的1对应的V3顶点未访问,访问该顶点:


V1
V2 V4
V1 V2 V4 V5 V3


6、至此,访问完了图中的所有顶点,即深度优先搜索序列为V1、V2、V4、V5、V3。


✨对于深度优先搜索(DFS),由于基于邻接表的遍历得到的序列可能不是唯一的,即根据边的输入次序不同,从而得到的邻接表不同,从而遍历序列不一样;而基于邻接矩阵所得到的DFS遍历序列是唯一的。


(二)深度优先生成树、森林


对一个连通图或非连通图进行DFS遍历后,若将在遍历过程中所经历过的顶点保留,则可以形成一棵树或森林,即深度优先生成树或深度优先生成森林;另外,基于邻接表存储的深度优先生成树或深度优先生成森林也是不唯一的;而对于邻接矩阵则是唯一的。

例如,上面这个无向连通图遍历DFS遍历生成的深度优先生成树如下(基于邻接表):

1667295759023.jpg

例如,对于上面这个有向图进行DFS遍历:

1667295768392.jpg

它并不是连通图,得到的深度优先生成森林如下:

1667295777069.jpg


(三)DFS的空间复杂度和时间复杂度


对于一个图G=(V,E),由顶点集V和边集E组成。

1、DFS算法的空间复杂度


✨由于DFS算法是一个递归算法,即递归顶点集V,通过DFS遍历的空间复杂度为O(|V|)。

2、DFS算法的时间复杂度


✨时间复杂度取决于图的存储结构,若通过邻接矩阵表示图,则查找顶点的邻接顶点所需时间为O(|V|),总时间复杂度为O(|V2|)(邻接矩阵为方阵n×n);若通过邻接表表示图,则查找所有顶点的邻接顶点所需时间为O(|E|),访问顶点所需时间为O(|V|),即总时间复杂度为O(|V|+|E|)。


三、广度优先搜索(BFS)


(一)BFS算法步骤


前面文章中,讲到过二叉树的层序遍历,其实这里图的广度优先搜索(BFS)是由其推广而来的。


二叉树的层序遍历中,层次优先,当对一层的结点都遍历完后,遍历下一层,按照次序对每个结点的左、右孩子进行遍历。


图的广度优先搜索中需要借助到队列来遍历,首先选取一个起始点顶点vi,访问后将其入队并标记为已访问(使用队列用于避免重复访问,存放已经访问过的各邻接顶点);当队列不为空时检查出队顶点的所有邻接顶点,访问未被访问的邻接顶点并将其入队,……,继续重复该过程,直到图中所有与vi连通的顶点都被访问到;当队列为空时跳出循环,则此时遍历完成。

可以知道BFS算法并不是递归过程,且要用到队列。


1、邻接表BFS算法步骤

例如下面这个无向图:

1667295828963.jpg

该图的邻接表如下:

1667295840759.jpg

通过邻接表进行广度优先搜索的步骤如下(这里以V1为访问起始点,不唯一):

1、首先访问0,即V1,访问后标记已访问过,使其入队,然后删除当前队头结点;【V1】

2、遍历V1单链表,使其未访问的邻接顶点2、1入队并标记;【V2、V3】

3、访问队头结点1并删除,然后遍历1对应的V2单链表,使其未访问的邻接顶点4、3入队并标记;【V3、V4、V5】

4、访问队头结点2并删除,然后遍历2对应的V3单链表,使其未访问的邻接顶点6、5入队并标记;【V4、V5、V6、V7】

5、访问队头结点3并删除,然后遍历3对应的V4单链表,使其未访问的邻接顶点7入队并标记;【V5、V6、V7、V8】

6、访问队头结点4并删除,然后遍历4对应的V5单链表,该单链表中无未访问的顶点;【V6、V7、V8】

7、访问队头结点5并删除,然后遍历5对应的V6单链表,该单链表中无未访问的顶点;【V7、V8】

8、访问队头结点6并删除,然后遍历6对应的V7单链表,该单链表中无未访问的顶点;【V8】

9、访问队头结点7并删除,然后遍历7对应的V8单链表,该单链表中无未访问的顶点,此时队列为空,遍历结束;【】

故该图的深度优先遍历序列为:V1、V2、V3、V4、V5、V6、V7、V8。


2、邻接矩阵BFS算法步骤

通过图的邻接矩阵实现广度优先搜索,例如下面这个图(以V1为访问起始点,是唯一的):


例如,对于下面这个有向图,对其进行广度优先搜索:

1667295850643.jpg


其邻接矩阵如下:

1667295865296.jpg

1、由V1行开始,如下表:

V1



2、可得与其匹配的有V2、V3,填到表中V1之后:

V1 V2 V3



3、由V2行开始,其中V4未访问,填到V3之后:

V1 V2 V3 V4


4、由V3行开始,都为0,继续下一行。

5、由V4行开始,其中V5未访问,填到V4之后:

V1 V2 V3 V4 V5


6、至此,该图的所有顶点都已访问到,得到的序列便是广度优先搜索,即深度优先搜索序列为V1、V2、V3、V4、V5。


✨同样,对于广度优先搜索,由于基于邻接表的遍历得到的序列可能不是唯一的,即根据边的输入次序不同,从而得到的邻接表不同,从而遍历序列不一样;而基于邻接矩阵所得到的遍历序列是唯一的,这两点和深度优先搜索遍历是一样的。


(二)广度优先生成树、森林


与DFS遍历一样, 对一个连通图或非连通图进行BFS遍历后,若将在遍历过程中所经历过的顶点保留,则可以形成一棵树或森林,即广度优先生成树或广度优先生成森林;另外,基于邻接表存储的广度优先生成树或广度优先生成森林也是不唯一的;而对于邻接矩阵则是唯一的。

例如,上面这个无向连通图遍历BFS遍历生成的深度优先生成树如下(基于邻接表):

1667295922869.jpg

例如,对于上面这个有向图进行BFS遍历:

1667295931980.jpg

它并不是连通图,得到的广度优先生成森林如下:

1667295940343.jpg


例如写出下面这个图的广度优先遍历序列:

1667295948004.jpg


其广度优先遍历序列为:0,4,3,2,1,6,5,9,8,7。


(三)BFS的空间复杂度和时间复杂度


对于一个图G=(V,E),由顶点集V和边集E组成。

1、BFS算法的空间复杂度


✨通过BFS遍历的空间复杂度为O(|V|)。

2、BFS算法的时间复杂度


✨时间复杂度取决于图的存储结构,若通过邻接矩阵表示图,则查找顶点的邻接顶点所需时间为O(|V|),总时间复杂度为O(|V2|)(邻接矩阵为方阵n×n),这和DFS算法的时间复杂度是一样的;若通过邻接表表示图,则每个顶点都入队一次,即所需时间为O(|V|),搜索顶点的邻接顶点所需时间为O(|E|),其时间复杂度为O(|V|+|E|)。


四、DFS和BFS的应用


以上两种遍历算法都可以用于判断图的连通性,可计算图中的连通分量数目,当一个图为连通图时,经过遍历后会访问到所有的顶点,其中访问过的顶点不会再次访问,从而可以得到图中的连通分量数目。


相关文章
|
2月前
|
算法 测试技术 定位技术
数据结构与算法——DFS(深度优先搜索)
数据结构与算法——DFS(深度优先搜索)
|
1月前
|
算法 安全 网络安全
数据结构之网络攻击路径(深度优先搜索)
本文介绍了如何使用深度优先搜索(DFS)算法分析网络攻击路径。在网络安全领域,DFS用于检测网络中潜在的攻击路径,帮助安全人员及时发现并阻止威胁。文中详细描述了网络图的构建、节点间的连接关系以及DFS的实现过程。通过一个具体的例子,展示了如何检测从一个普通节点到关键节点的攻击路径,并讨论了DFS算法的优缺点。提供的C++代码实现了网络图的构建和攻击路径的检测功能。
67 24
|
1月前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。
53 0
|
1月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
102 23
|
1月前
|
传感器 算法
数据结构之环境监测系统(深度优先搜索)
环境监测系统采用深度优先搜索(DFS)算法,实现实时监测和分析环境参数,如温度、湿度等。系统通过构建传感器网络图结构,利用DFS遍历网络,检测异常数据。当温度超过预设阈值时,系统将发出警告。此系统适用于工业生产、室内空调控制、农业温室管理等多种场景,提供高效的环境监测解决方案。
49 12
|
1月前
|
算法
数据结构之旅行商问题(深度优先搜索)
旅行商问题(TSP)是寻找访问多个城市并返回起点的最短路径的经典问题。本文介绍了TSP的背景、应用、复杂性和解决方法,重点讲解了使用深度优先搜索(DFS)算法求解TSP的过程。通过邻接矩阵表示城市间的距离,利用访问数组和栈结构辅助DFS遍历,最终找到最优路径。此方法虽然能保证找到最优解,但时间复杂度高,适用于城市数量较少的情况。示例代码展示了算法的具体实现及结果分析。
51 2
|
1月前
|
算法
数据结构之农业作物管理(深度优先搜索)
本文探讨了农业作物管理系统的背景、发展动因及其在现代农业中的重要性,特别是在应对气候变化、资源减少等挑战时的作用。文中介绍了作物关系建模与深度优先搜索(DFS)的应用,展示了如何通过邻接矩阵和DFS算法实现作物的智能管理和优化。通过具体的数据结构设计和核心代码实现,说明了DFS在农业作物管理中的应用效果及优缺点。
37 1
|
2月前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
3月前
|
存储 JSON NoSQL
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记,包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景,并通过命令示例演示了如何在Redis中操作这些数据结构。此外,还提供了一些练习示例,帮助读者更好地理解和应用这些数据结构。
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
34 0