广度优先遍历树算法

Ⅰ 广度优先遍历是什么

1.广度优先遍历的思想广度优先遍历类似树的按层次遍历。设初始状态时图中的所有顶点未被访问，则算法思想为：首先访问图中某指定的起始顶点v，并将其标记为已访问过，然后由v出发依次访问v的各个未被访问的邻接点v1，v2，…，vk；并将其均标识为已访问过，再分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v路径相通的顶点都被访问到。

若G是连通图，则遍历完成；否则，在图G中另选一个尚未访问的顶点作为新源点继续上述搜索过程，直至图G中所有顶点均被访问为止。

2.广度优先遍历示例例如，对图7－18（a）所示的图G，假设指定从顶点v1开始进行广度优先遍历，首先访问v1，因与v1相邻并且未被访问过的顶点有v2和v6，则访问v2和v6，然后访问与v2相邻并未访问的邻接点v2，v7，再访问与v6相邻并且未被访问过的邻接点v5，按这样的次序依次访问与v2相邻并且未被访问过的邻接点v4，v8，与v7相邻并且未被访问过的邻接点v9，此时，与v5，v4，v8，v9相邻并且未被访问过的邻接点没有了，即图G中的所有顶点访问完，其遍历序列为：v1－＞v2－＞v6－＞v2－＞v7－＞v5－＞v4－＞v8－＞v9。这种顺序不是唯一的，如果从v1出发后，相邻的多个顶点优先选择序号大的顶点访问，其遍历序列为：v1－＞v6－＞v2－＞v5－＞v7－＞v2－＞v4－＞v9－＞v8。同理，图7－18（b）是假设从v1开始，相邻的多个顶点优先选择序号小的顶点访问，其遍历序列为：v1－＞v2－＞v2－＞v4－＞v5－＞v6－＞v7－＞v8；相邻的多个顶点优先选择序号大的顶点访问，其遍历序列为：v1－＞v2－＞v2－＞v7－＞v6－＞v5－＞v4－＞v8。图7－18（c）假设从a开始，相邻的多个顶点优先选择ASCII码小的顶点访问，其遍历序列为：a－＞b－＞d－＞e－＞f－＞c－＞g；相邻的多个顶点优先选择ASCII码大的顶点访问，其遍历序列为：a－＞f－＞e－＞d－＞b－＞g－＞c。

2.广度优先遍历的算法在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的邻接点。应利用一个队列结构记录顶点的访问顺序，将访问的每个顶点入队，然后再依次出队。

在广度优先遍历过程中，为了避免重复访问某个顶点，也需要创建一个一维数组visited［n］（n是图中顶点的数目），用来记录每个顶点是否已被访问过。

Ⅱ 广度优先算法

广度优先算法（Breadth-First Search），同广度优先搜索，又称作宽度优先搜索，或横向优先搜索，简称BFS，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果发现目标，则演算终止。广度优先搜索的实现一般采用open-closed表。

Ⅲ 深度优先遍历与广度优先遍历的区别

一、指代不同

1、深度优先遍历：是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

2、广度优先遍历：系统地展开并检查图中的所有节点，以找寻结果。

二、特点不同

1、深度优先遍历：所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分──控制结构和产生系统。正如前面所说的，搜索算法简而言之就是穷举所有可能情况并找到合适的答案，所以最基本的问题就是罗列出所有可能的情况，这其实就是一种产生式系统。

2、广度优先遍历：并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

三、算法不同

1、深度优先遍历：把根节点压入栈中。每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。找到所要找的元素时结束程序。如果遍历整个树还没有找到，结束程序。

2、广度优先遍历：把根节点放到队列的末尾。每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。找到所要找的元素时结束程序。如果遍历整个树还没有找到，结束程序。

Ⅳ JS树结构数据的遍历

title: JS树结构数据的遍历
date: 2022-04-14
description: 针对项目中出现树形结构数据的时候，我们怎样去操作他

项目中我们会经常出现对树形结构的遍历、查找和转换的场景，比如说DOM树、族谱、社会机构、组织架构、权限、菜单、省市区、路由、标签等等。那针对这些场景和数据，我们又如何去遍历和操作，有什么方式或者技巧可以简化我们的实现思路。下面我们将针对常规出现的场景去总结一下我们的遍历方式

树的特点
1、每个节点都只有有限个子节点或无子节点；
2、没有父节点的节点称为根节点；
3、每一个非根节点有且只有一个父节点；
4、除了根节点外，每个子节点可以分为多个不相交的子树；
5、树里面没有环路

下面的图片表示一颗树

在下面的JS中我们由多棵树组成我们的数据

在这数据中我们如何评判数据是否为叶节点（也就是最后一级），我们每个节点都会存在children属性，如果不存在children属性或者children不是一个数组或者children为数组且长度为0我们则认为他是一个叶节点

我们针对树结构的操作离不开遍历，遍历的话又分为广度优先遍历、深度优先遍历。其中深度优先遍历可以通过递归和循环的方式实现，而广度优先遍历的话是非递归的

从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。即访问树结构的第n+1层前必须先访问完第n层。

简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。

所以我们的实现思路是，维护一个队列，队列的初始值为树结构根节点组成的列表，重复执行以下步骤直到队列为空：
取出队列中的第一个元素，进行访问相关操作，然后将其后代元素（如果有）全部追加到队列最后。

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止

1、先序遍历
访问子树的时候，先访问根再访问根的子树

2、后序遍历
访问子树的时候，先访问子树再访问根

1、先序遍历
先序遍历与广度优先循环实现类似，要维护一个队列，不同的是子节点不追加到队列最后，而是加到队列最前面

2、后序遍历
后序遍历就略微复杂一点，我们需要不断将子树扩展到根节点前面去，执行列表遍历，并且通过一个临时对象维护一个id列表，当遍历到某个节点如果它没有子节点或者它本身已经存在于我们的临时id列表，则执行访问操作，否则继续扩展子节点到当前节点前面

对于树结构的遍历操作，其实递归是最基础，也是最容易理解的。递归本身就是循环的思想，所以可以用循环来改写递归,以上的方式在项目中已经廊括了大部分的场景了，我们在日常开发中可以根据场景或者需要去选择我们的遍历方式，或者基于此对他进行调整和优化，至于每种方式的空间复杂度和时间复杂度我们在这个地方就不去尝试了，各位感兴趣可以自己去验证。

广度优先搜索

树的遍历

深度优先搜索

图文详解两种算法：深度优先遍历（DFS）和广度优先遍历（BFS）

二叉树遍历（前序，后序，中序，层次）递归与迭代实现JavaScript

JS树结构操作:查找、遍历、筛选、树和列表相互转换

Ⅳ 基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）

        深度优先搜索和广度优先搜索，都是图形搜索算法，它两相似，又却不同，在应用上也被用到不同的地方。这里拿一起讨论，方便比较。

一、深度优先搜索

        深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

基本步奏

（1）对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。

（2）从stack中访问栈顶的点；

（3）找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行；

（4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；

（5）直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。

二、广度优先搜索

        广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

基本步奏

（1）给出一连通图，如图，初始化全是白色（未访问）；

（2）搜索起点V1（灰色）；

（3）已搜索V1（黑色），即将搜索V2，V3，V4（标灰）；

（4）对V2，V3，V4重复以上操作；

（5）直到终点V7被染灰，终止；

（6）最短路径为V1，V4，V7.

Ⅵ 无向有权的图的深度、广度优先遍历怎么做的啊，他的遍历序列怎么求呢

总结深度优先与广度优先的区别
1、区别

1） 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。

2） 深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下：

先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

3）深度优先搜素算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。

广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。

Ⅶ Python数据结构-队列与广度优先搜索（Queue）

队列（Queue） ：简称为队，一种线性表数据结构，是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。
我们把队列中允许插入的一端称为 “队尾（rear）” ；把允许删除的另一端称为 “队头（front）” 。当表中没有任何数据元素时，称之为 “空队” 。

广度优先搜索算法（Breadth First Search） ：简称为 BFS，又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始，沿着树的宽度遍历树或图的节点。如果所有节点均被访问，则算法中止。

广度优先遍历 类似于树的层次遍历过程 。呈现出一层一层向外扩张的特点。先看到的节点先访问，后看到的节点后访问。遍历到的节点顺序符合“先进先出”的特点，所以广度优先搜索可以通过“队列”来实现。

力扣933

游戏时，队首始终是持有薯仔的人
模拟游戏开始，队首的人出队，之后再到队尾（类似于循环队列）
传递了num次之后，将队首的人移除
如此反复，直到队列中剩余一人

多人共用一台打印机，采取“先到先服务”的队列策略来执行打印任务
需要解决的问题：1 打印系统的容量是多少？2 在能够接受的等待时间内，系统可容纳多少用户以多高的频率提交打印任务？

输入：abba
输出：False
思路：1 先将需要判定的词从队尾加入 deque; 2从两端同时移除字符并判断是否相同，直到deque中剩余0个（偶数）或1个字符（奇数）

内容参考： https://algo.itcharge.cn/04.%E9%98%9F%E5%88%97/01.%E9%98%9F%E5%88%97%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/01.%E9%98%9F%E5%88%97%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/

Ⅷ 图的广度优先遍历为什么w加一

一 图的广度优先遍历基本思想
1 图的广度优先搜索(Broad First Search) ，简称BFS。

2 该遍历类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。

二 广度优先遍历算法步骤
1 访问初始结点v并标记结点v为已访问。

2 结点v入队列。

3 当队列非空时，继续执行，否则算法结束。

4 出队列，取得队头结点u。

5 查找结点u的第一个邻接结点w。

6 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：

6.1 若结点w尚未被访问，则访问结点w并标记为已访问。

6.2 结点w入队列。

6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

三 实战
1 需求
用广度优先算法实现下图。

2 代码
3 测试

Ⅸ 广度优先搜索有什么难点

广度优先搜索难点在于每一种算法的不同，树的遍历。

扩展知识：

广度优先搜索算法又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。

广度优先搜索算法主要有四个特性：

空间复杂度：由于对空间的大量需求，因此BFS并不适合解非常大的问题，对于类似的问题，应用IDDFS已达节省空间的效果。

时间复杂度：最差情形下，BFS必须查找所有到可能节点的所有路径。

完全性：广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。

最佳解：若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS并不一定回传最佳解。

Ⅹ 深度优先遍历怎么修改为广度优先遍历

假设初始状态是图中所有顶点均未被访问
从某个顶点出发，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。
若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
实现深度优先遍历的关键在于回溯。所谓“回溯”，就是自后往前，追溯曾经走过的路径。

算法特点
深度优先搜索是一个递归的过程。

首先，选定一个出发点后进行遍历，如果有邻接的未被访问过的节点则继续前进。
若不能继续前进，则回退一步再前进
若回退一步仍然不能前进，则连续回退至可以前进的位置为止。
重复此过程，直到所有与选定点相通的所有顶点都被遍历。
深度优先搜索是递归过程，带有回退操作，因此需要使用栈存储访问的路径信息。当访问到的当前顶点没有可以前进的邻接顶点时，需要进行出栈操作，将当前位置回退至出栈元素位置。

图解过程
无向图的深度优先遍历
以下图所示无向图说明深度优先搜索遍历过程。

实例一

在这里插入图片描述
假设我们从顶点A开始，遍历过程中的每一步如下：

首先选取顶点A为起始点，输出A顶点信息，而且将A入栈，并且标记A为已访问顶点
A的邻接顶点有C、D、F，从中任意选取一个顶点前进。这里我们选取C为前进位置顶点。输出C顶点信息，将C入栈，并标记C为已访问顶点。当前位置指向顶点C
顶点C的邻接顶点有A、D、B，此时A已经标记为已访问顶点，因此不能继续访问。从B或者D中选取一个顶点前进，这里我们选取B顶点为前进位置顶点。输出B顶点信息，将B入栈，标记B顶点为已访问顶点。当前位置指向B
顶点B的邻接顶点只有C、E，C已被标记，不能继续访问，因此选取E为前进位置顶点，输出E顶点信息，将E入栈，标记E顶点，当前位置指向E。
顶点E的邻接顶点均已被标记，此时无法继续前进，则需要进行回退。将当前位置回退至顶点B，回退的同时将E出栈。
顶点B的邻接顶点也均被标记，需要继续回退，当前位置回退至C，回退同时将B出栈。
顶点C可以前进的顶点位置为D，则输出D顶点信息，将D入栈，并标记D顶点。当前位置指向顶点D。
顶点D没有前进的顶点位置，因此需要回退操作。将当前位置回退至顶点C，回退同时将D出栈。
顶点C没有前进的顶点位置，继续回退，将当前位置回退至顶点A，回退同时将C出栈。
顶点A前进的顶点位置为F，输出F顶点信息，将F入栈，并标记F。将当前位置指向顶点F。
顶点F的前进顶点位置为G，输出G顶点信息，将G入栈，并标记G。将当前位置指向顶点G。
顶点G没有前进顶点位置，回退至F。当前位置指向F，回退同时将G出栈。
顶点F没有前进顶点位置，回退至A，当前位置指向A，回退同时将F出栈。
顶点A没有前进顶点位置，继续回退，栈为空，则以A为起始的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。
采用深度优先搜索遍历顺序为A->C->B->E->D->F->G。
利用一个临时栈来实现回溯，最终遍历完所有顶点

问题：

（1）必须选取A作为遍历的起点吗？

不是原则我们可以选取任何一个节点作为起点进行开始，进行深度优先遍历
（2）当有多个邻接点未被访问时，可以选取哪个作为下一个起点呢？

随便哪个都行。
当有多个临界点可选时，相当于走迷宫时出现了多个分叉路口，我们只要不走之前走过的路就行了。所以关键在于标记哪个点是否已经走过。不过，一般我们会定义一个原则，必须不碰重复点的情况下，选择走左/右手第一条没有走过的路，这样比较好理解
两个原则：

右手原则： 在没有碰到重复顶点的情况下，分叉路口始终是向右手边走，每路过一个顶点就做一个记号
左手原则： 在没有碰到重复顶点的情况下，分叉路口始终是向左手边走，每路过一个顶点就做一个记号
下面以右手原则进行深度优先遍历再看个例子

实例二

在这里插入图片描述

原则我们可以选取任何一个节点作为起点进行开始，进行深度优先遍历，假设我们从顶点A开始，遍历过程中的每一步如下：

第一步：从顶点A开始，将顶点A标记为已访问节点

第二步：根据右手原则，访问顶点B，并将B标记为已访问节点

第三步：右手原则，访问顶点C

第四步：右手原则，访问顶点D

第五步：右手原则，访问顶点E

第六步：右手原则，访问顶点F
在这里插入图片描述

第七步：右手原则，应该先访问顶点F的邻接顶点A，但发现A已经被访问，则访问A之外的最右侧顶点G
在这里插入图片描述

第八步：右手原则，先访问顶点B，顶点B已经被访问；在访问顶点D，顶点D已经被访问；最后访问顶点H
在这里插入图片描述

第九步：发现顶点H的邻接顶点均已被访问，则退回到顶点G;

第十步：顶点G的邻接顶点均已被访问，则退回到顶点F；

第十一步：顶点F的邻接顶点已被访问，则退回到顶点E；

第十二步：顶点E的邻接顶点均已被访问，则退回到顶点D；

第十三步：顶点D的邻接顶点I尚未被访问，则访问顶点I；
在这里插入图片描述

第十四步：顶点I的邻接顶点均已被访问，则退回到顶点D;

第十五步：顶点D的邻接顶点均已被访问，退回到顶点C；

第十六步：顶点C的邻接顶点均已被访问，则退回到顶点B；

顶点B的邻接顶点均已被访问，则退回到顶点A，顶点A为起始顶点，深度优先搜索结束。

图的深度优先搜索和二叉树的前序遍历、中序遍历、后序遍历本质上均属于一类方法。

上面的过程可以总结为以下3个步骤：

首先选定一个未被访问过的顶点V作为起始顶点（或者访问指定的起始顶点V），并将其标记为已访问

然后搜索与顶点V邻接的所有顶点，判断这些顶点是否被访问过，如果有未被访问过的顶点W；再选取与顶点W邻接的未被访问过的一个顶点并进行访问，依次重复进行。当一个顶点的所有的邻接顶点都被访问过时，则依次回退到最近被访问的顶点。若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取出一个并重复上述过程，直到与起始顶点V相邻接的所有顶点都被访问过为止。

若此时图中依然有顶点未被访问，则再选取其中一个顶点作为起始顶点并进行遍历，转（2）。反之，则遍历结束。

有向图深度优先搜索
在这里插入图片描述
（1）以顶点A为起始点，输出A，将A入栈，并标记A为已经访问。当前位置指向A。

（2）以A为尾的边只有1条，且边的头为顶点B，则前进位置为顶点B，输出B，将B入栈，标记B。当前位置指向B。

（3）顶点B可以前进的位置有C与F，选取F为前进位置，输出F，将F入栈，并标记F。当前位置指向F。

（4）顶点F的前进位置为G，输出G，将G入栈，并标记G。当前位置指向G。

（5）顶点G没有可以前进的位置，则回退至F，将G出栈。当前位置指向F。

（6）顶点F没有可以前进的位置，继续回退至B，将F出栈。当前位置指向B。

（7）顶点B可以前进位置为C和E，选取E，输出E，将E入栈，并标记E。当前位置指向E。

（8）顶点E的前进位置为D，输出D，将D入栈，并标记D。当前位置指向D。

（9）顶点D的前进位置为C，输出C，将C入栈，并标记C。当前位置指向C。

（10）顶点C没有前进位置，进行回退至D，回退同时将C出栈。

（11）继续执行此过程，直至栈为空，以A为起始点的遍历过程结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。

性能分析
当图采用邻接矩阵存储时，由于矩阵元素个数为n 2 n^2n
2
，因此时间复杂度就是O ( n 2 ) O(n^2)O(n
2
)

当图采用邻接表存储时，邻接表中只是存储了边结点(e条边，无向图也只是2e个结点)，加上表头结点为n（也就是顶点个数），因此时间复杂度为O(n+e)。

广度优先搜索
算法思想
思想：
从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点
然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
实现广度优先遍历的关键在于回放。
回溯与重放是完全相反的过程。

仍然以刚才的图为例，按照广度优先遍历的思想

我们先遍历顶点0，然后遍历其邻接点1、3
接下来我们要遍历更外围的顶点，可是如何找到这些更外围的顶点呢？我们需要把刚才遍历过的顶点1,3按照顺序回顾一遍，从顶点1发现了邻接点2，从顶点3发现了邻接点4。于是得到了顺序2,4
再把刚才遍历过的顶点2，4按照顺序回顾一遍，分别得到邻接点5，6
再把刚才遍历过的顶点5，7按照顺序回顾一遍，分别得到邻接点7，7。7只需要打印一次，所以我们需要一个东西来标记当前顶点是否已经访问过
在这里插入图片描述

像这样把遍历过的顶点按照之前的遍历顺序重新回顾，就叫做重放。

同样的，要实现重放也需要额外的存储空间，可以利用队列的先入先出特性来实现。
另外，还需要标记某个点是否已经被访问过，可以用数组、set等来实现
可以看出，广度优先搜索它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

算法特点
广度优先搜索类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。

图解过程
无向图的广度优先搜索
在这里插入图片描述

（1）选取A为起始点，输出A，A入队列，标记A，当前位置指向A。

在这里插入图片描述

（2）队列头为A，A出队列。A的邻接顶点有B、E，输出B和E，并将B和E入队，以及标记B、E为已访问。当前位置指向B。
在这里插入图片描述
（3）队列头为B，B出队列。B的邻接顶点有C、D，输出C、D，将C、D入队列，并标记C、D。当前位置指向B。

在这里插入图片描述

（4）队列头为E，E出队列。E的邻接顶点有D、F，但是D已经被标记，因此输出F，将F入队列，并标记F。当前位置指向E。

在这里插入图片描述
（5）队列头为C，C出队列。C的邻接顶点有B、D，但B、D均被标记。无元素入队列。当前位置指向C。

在这里插入图片描述
（6）队列头为D，D出队列。D的邻接顶点有B、C、E，但是B、C、E均被标记，无元素入队列。当前位置指向D。
在这里插入图片描述
（7）队列头为F，F出队列。F的邻接顶点有G、H，输出G、H，将G、H入队列，并标记G、H。当前位置指向F。
在这里插入图片描述
（8）队列头为G，G出队列。G的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向G。
在这里插入图片描述
（9）队列头为H，H出队列。H的邻接顶点有F，但F已被标记，无元素入队列。当前位置指向H。
在这里插入图片描述
（10）队列空，则以A为起始点的遍历结束。若图中仍有未被访问的顶点，则选取未访问的顶点为起始点，继续执行此过程。直至所有顶点均被访问。

有向图的广度优先搜索
在这里插入图片描述
（1）选取A为起始点，输出A，将A入队列，标记A。

在这里插入图片描述
（2）队列头为A，A出队列。以A为尾的边有两条，对应的头分别为B、C，则A的邻接顶点有B、C。输出B、C，将B、C入队列，并标记B、C。

在这里插入图片描述

（3）队列头为B，B出队列。B的邻接顶点为C，C已经被标记，因此无新元素入队列。

在这里插入图片描述
（4）队列头为C，C出队列。C的邻接顶点有E、F。输出E、F，将E、F入队列，并标记E、F。

在这里插入图片描述
（5）列头为E，E出队列。E的邻接顶点有G、H。输出G、H，将G、H入队列，并标记G、H。

在这里插入图片描述
（6）队列头为F，F出队列。F无邻接顶点

在这里插入图片描述

（7）队列头为G，G出队列。G无邻接顶点

在这里插入图片描述
（8）队列头为H，H出队列。H邻接顶点为E，但是E已被标记，无新元素入队列

在这里插入图片描述
（9）队列为空，以A为起始点的遍历过程结束，此时图中仍有D未被访问，则以D为起始点继续遍历。选取D为起始点，输出D，将D入队列，标记D

在这里插入图片描述
（10）队列头为D，D出队列，D的邻接顶点为B，B已被标记，无新元素入队列

在这里插入图片描述
（11）队列为空，且所有元素均被访问，广度优先搜索遍历过程结束。广度优先搜索的输出序列为：A->B–>C->E->F->G->H->D。

算法分析
我们来看下，广度优先搜索的时间、空间复杂度是多少呢？假设图有V个顶点，E条边

每个顶点都需要进出一遍队列，每个边都会被访问一次。所以，广度优先搜索的时间复杂度是O(V+E)。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)
广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列上。这两个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。
总结
图的遍历主要就是这两种遍历思想，深度优先搜索使用递归方式，需要栈结构辅助实现。广度优先搜索需要使用队列结构辅助实现。在遍历过程中可以看出，

对于连通图，从图的任意一个顶点开始深度或广度优先遍历一定可以访问图中的所有顶点
对于非连通图，从图的任意一个顶点开始深度或广度优先遍历并不能访问图中的所有顶点。
实现
深度优先遍历
当图采用邻接矩阵进行存储，递归的实现操作：

#define MAXVBA 100
#define INFINITY 65536

typedef struct {
char vexs[MAXVBA];
int arc[MAXVBA][MAXVBA];
int numVertexes, numEdges;
} MGraph;

// 邻接矩阵的深度有限递归算法

#define TRUE 1
#define FALSE 0
#define MAX 256

typedef int Boolean; // 这里我们定义Boolean为布尔类型，其值为TRUE或FALSE
Boolean visited[MAX]; // 访问标志的数组

void DFS(MGraph G, int i){
visited[i] = TRUE;
printf("%c", G.vexs[i]);

for (int j = 0; j < G.numVertexes; ++j) {
if (G.arc[i][j] == 1 && !visited[j]){
DFS(G, j); // 对为访问的邻接顶点递归调用
}
}
}

// 邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G){
int i;

// 初始化所有顶点状态都是未访问过状态
for (i = 0; i < G.numVertexes; ++i) {
visited[i] = FALSE;
}

//防止图为非联通的情况，遍历整个图
for (i = 0; i < G.numVertexes; ++i) {
if (!visited[i]){ // 若是连通图，只会执行一次
DFS(G, i);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
当图采用邻接矩阵进行存储，栈的实现操作：

void DFS_Stack(MGraph G, int i)
{
int node;
int count = 1;
printf("%c ", G.vexs[i]); // 打印已访问顶点
visited[i] = TRUE;
node = i;
push(i); //开始的节点入栈
while(count < G.numVertexes) //still has node not visited
{
/* 所有被访问的节点依次入栈，只有node当找不到下一个相连的节点时，才使用出栈节点 */
for(j=0; j < G.numVertexes; j++)
{
if(G.arc[node][j] == 1 && visited[j] == FALSE)
{
visited[j] = TRUE;
printf("%c ", G.vexs[j]);
count++;
push(j); //push node j
break;
}
}
if(j == G.numVertexes) //与node相连的顶点均已被访问过，所以需要从stack里取出node的上一个顶点，再看该顶点的邻接顶点是否未被访问
node = pop();
else //找到与node相连并且未被访问的顶点，
node = j;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
请添加图片描述
邻接表存储下图的深度优先搜索代码实现，与邻接矩阵的思想相同，只是实现略有不同：

// 邻接表的深度有限递归算法

#define TRUE 1
#define FALSE 0
#define MAX 256

typedef int Boolean; // 这里我们定义Boolean为布尔类型，其值为TRUE或FALSE
Boolean visited[MAX]; // 访问标志的数组

void DFS(GraphAdjList GL, int i)
{
EdgeNode *p;

visited[i] = TRUE;
printf("%c " GL->adjList[i].data);
p = GL->adjList[i].firstEdge;

while(p)
{
if( !visited[p->adjvex] )
{
DFS(GL, p->adjvex);
}
p = p->next;
}
}

// 邻接表的深度遍历操作
void DFSTraverse(GraphAdjList GL)
{
int i;

for( i=0; i < GL->numVertexes; i++ )
{
visited[i] = FALSE; // 初始化所有顶点状态都是未访问过状态
}

for( i=0; i < GL->numVertexes; i++ )
{
if( !visited[i] ) // 若是连通图，只会执行一次
{
DFS(GL, i);
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
广度优先遍历
请添加图片描述

// 邻接矩阵的广度遍历算法
void BFSTraverse(MGraph G)
{
int i, j;
Queue Q;

for( i=0; i < G.numVertexes; i++ )
{
visited[i] = FALSE;
}

initQueue( &Q );

for( i=0; i < G.numVertexes; i++ )
{
if( !visited[i] )
{
printf("%c ", G.vex[i]);
visited[i] = TRUE;
EnQueue(&Q, i);

while( !QueueEmpty(Q) )
{
DeQueue(&Q, &i);
for( j=0; j < G.numVertexes; j++ )
{
if( G.art[i][j]==1 && !visited[j] )
{
printf("%c ", G.vex[j]);
visited[j] = TRUE;
EnQueue(&Q, j);
}
}
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
原文链接：https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw%3D%3D&chksm=db828f&idx=1&mid=2653197523&scene=21&sn=#wechat_redirect