2022.4.3

WEEK10.1 图的遍历

一、内容

1.深度优先搜索（DFS）

我们上节课讲过，我们这里再复习一下。
所谓深度优先，就是先一条路走到底，然后再返回寻找可以继续走到底的路
进行DFS时，一定要注意对已经访问的节点进行标记

2.图的类似树的遍历

我们之前讲树的时候，学了很多的遍历方法，如前序、中序、后序、层序。
而树是一种特殊的图，我们对于图，也应该有这种遍历方法
来一个题目看看吧

以2为顶点进行层序遍历 问哪一个选项不是层序遍历？

答案是B！4的深度比5高，理论上4不会比5优先出现！
注意，同层次的顺序不重要，但不同层次的顺序很重要

如果是这样的图呢？以上哪个选项是以2为顶点的层序遍历？

答案是A！

再来一个，请问此图的从0开始的后序遍历是什么 注意这里有一个邻接链表，想一想这个邻接链表有什么用！

选D！注意邻接链表，首先访问的是1！

3.拓扑排序（Topological Sort）

将一个图以箭头顺序排序。注意这个排序结果不唯一

比如这个图 符合拓扑排序的结果有如图所示

可见，我们都是从入度为0的节点开始进行拓扑排序，然后根据箭头指向一步步排序。
这里老师给我们了一种排序方法：
（1）对一个（任何一个都可以，但注意有多个的情况）入度为0的点开始DFS
（2）完成之后，我们要看是否还有没有访问到的点，若无，结束；若有，“重启”，从这个节点开始DFS
（3）循环2、3步，直到都访问。此时输出数组类似一个DFS的数组（只是多了重启的访问）。
（4）将这个数组翻转（字面意思），就得到了topo排序

我们看一下到底是如何进行的

对一个节点开始DFS 此时一个DFS已经完成，但发现所有节点没有都访问，我们需要重启 从2开始重启（入度为0的节点），进行DFS。直到所有节点都访问。此时有一个输出数组 最后，我们翻转这个数组，于是得到我们需要的topo排序 排序后的简化图形

这个topo排序，用到了DFS，可见，DFS还是很重要的
注意在这一题，我们不能从2开始，因为此时3会在0前面，不符合要求（自己试试）

代码实现

4.广度优先排序（Breadth First Search——BFS）

这个有点类似树的层序遍历，但稍微有些不同

我们考虑使用一个队列（先进先出）来实现
先初始化一个队列，插入一个开始节点，并标记次节点。这里把队列称为fringe（中文意思是边界）
在队列被清空之前，我们会把旧节点v移出队列，继续把新的、未标记的v节点的相邻节点加入队列
下面看一个例子理解一下

如图，我们从0开始 然后检查0是否标记，没标记，则更新标记数组，并加入队列

注意我们发现一个可入队的节点后，我们先更新信息数组，再入队

然后将0移出队列，并将0的邻接节点且没标记的，即1节点，加入队列，并标记 在入队前更新数组 将1移出，并找未标记的相邻节点，即2、4，并入队 更新信息数组 然后2出队（因为2先入队，在4前面），并检查，发现5可以入队 在入队前记得更新数组

同理，之后就不说了
BFS运行时间消耗为 V + E

BFS代码实现