大家好！
数据结构与算法这一讲，我们继续第7章图的学习。我们来学习图的遍历。
在一个数据结构中，我们能够系统地访问其中的结点，
每个结点不重不漏地恰好访问而且只访问一次，这就是遍历。
那对于图的遍历，我们需要考虑的，就是，
图有连通的问题，还有回路的问题。
那怎么样解决这两个问题呢？我们可以加一个标记位。
在访问到了图的一个结点的时候，我们就给它标记为已访问。
对于回路的情况，我们如果下一次再回到了某一个点，
那我还想继续深入访问的时候呢，我就会可以退出了。
那对于这种不连通的情况，如果我们
把这个结点表呢，我都挨个地去查看一下所有的结点。
它如果是没有被访问，那我就进行一次
继续的遍历操作。这样的话呢，我们就是分成了几个不同的这样的连通分量，
来进行访问。那我们看一下图的遍历框架。首先我们把
这个标记数组都来设置为未访问的这个标记。
然后呢，我们对图的每一个点，都作为
起始的点来看待。那我们判断一下，这个点是不是
被访问过。如果被访问过，那么我们就放弃它。如果没有被访问过，
那么就作为我们这一个特殊的遍历算法，它的一个起始的源点。
那我们看一下这个深搜的这么一个过程。
深搜就是我们选择一个未访问点作为源点，然后我访问它，
然后，我们对这个点所关联到的其他的点，
又递归地进行一个深搜的访问。
那我们一直重复这个过程。一直到
以这个起始的源点为根的，这样的可达的这些子图都已经被访问过。
那接着，我们在去查询这个结点表的时候，
把那些未访问过的顶点作为源点，来继续
做深搜。那就是形成了一个一个的，这样的连通的这种，
子根图。然后，直到所有的这些顶点呢，都被访问过。
那我们看一下这个深搜的过程。那我实际上就是
一个回溯递归的过程。那我能进则进，从a，到b，到c，到f。
然后不能进的时候呢，我们就是在同层要换一个元素。
但是因为f到这个c来看呢，
那它是同层没有一个可换的，所以我们就退。
那再回到a，那我们换下一个是
d这个元素，这就完成了我们的一个，深搜的过程。
那深搜的一个算法框架就是
我们进到这样的一个算法里面。我先把自己标记为已访问。
而且，我现在就访问这个顶点。其实我这里可能就是直接打印它。
然后我看这个顶点，它关联到的其他点，
是不是没有被访问。如果没被访问呢，
那我就递归地进行深搜的访问。
访问完它的所有关联点以后，
整个这个结点，以及它所发出来的这些边
所关联到的子图结构呢，也就都被访问完毕了。
那这个时候我们可以进行一个后处理操作。
这个后处理，在我们后面拓扑排序的时候，我们就用到了这个后处理点。
宽搜，它的过程
是先从一个未访问点出发，然后我们访问这个结点，
以及，把它的这个相关联的这些点，
我们都给它相应地进行访问。
那我们一层一层就像这个波浪的涟漪一样，去
推进。我们直到这个从这个起始的源点v0出发的，
这样的可达路径上头的这些相关的点，都被访问过为止。
这个子图访问完了以后，如果还有其他的未达的这些顶点，
那我们就从顶点表里面再选择一个
未访问过的顶点作为源点，继续做广搜，直到这个图里面呢，所有结点都被访问过。
那我们来看一下这样的一个广搜的框架。首先，我
访问到这个结点呢，我先对它进行
一些操作，比如说打印它。然后我把它标记为已访问。把它入到队列里面。
当这个队列不空的时候，我们循环地去访问。首先，
把这个队首，
给它弹出来。然后，把这个弹出的这个元素
它作为顶点。它关联到的其他的顶点呢，我们都来判断一下，
这些关联点是不是已经被访问过。如果是没有被访问呢，
那我就访问这个相应的关联到的点。
而且，把它标记为已访问。再把它入到队列里面，等待下面进行继续处理
图的搜索算法，它的深搜和宽搜，都是
对每个顶点访问一次，而且每一条边，也是访问一次。
当然我们无向图的边呢，我其实一条边可以看做是两次的访问。
那采用邻接表的时候我们对于
有向图的这个总的代价呢是Θ(n+e)的。
而无向图呢，是Θ(n+2e)，其实也是Θ(n+2e)。
那我们可以看到呢，在相邻矩阵里面，
它处理这些边啊，需要Θ(n^2)的时间。
因为我们这个边是隐藏在这样的一个相邻矩阵里面。
那些零元素我们也要一个一个地看过去，它是一个双重的
这个for循环，对矩阵里面的每一个点都进行了一个观察。
所以它的总的时间代价是Θ(n^2)的，这个跟边是无关的。
如果对于，一个比较稀疏的图，
也就是边数e小于n方的时候，那明显地可以看出呢，
邻接表它是在存储上更有效的同时，它的算法也是更有效。
那我们再来看一种特殊的排序
也就是图的特殊的一种遍历的形式。
对于有向无环图，大家一定要注意这里
必须是有向的，而且是无环的图，才能做这样的拓扑排序。
如果图里面
有两个顶点，vi到vj，它们是有一条路径的。
我要求你遍历的这么一个结果呢，
是vi必须出现在vj之前。
那我们把vi当作vj的先决条件的话，
那其实这就是处理的一个先决条件的问题。
那我们所谓拓扑排序呢，就是不违反先决条件的情况下，
我们对整个这些结点呢，进行一个序列化的一个操作。
那我们来看一个排课的问题。假设，
一个学生他，在一段时间，比如说，一周他只能学一门课。
而且能学完。
那这些课之间呢，它有相应的这种先修的关系。
我们就可以形成这样的一个图结构，就是先修课的结构。
我们怎么样给他排课使得
这些先修课必须修完，才能够修后面的课。
比如说，我们要修C3这个课的时候呢，必须C1和C2已经都修完了。
那我们可以采用一个很显然的方法。
因为是有向无环图一定有
某个结点呢，它是不存在一个前趋的。
那它就是入度为0的这个点。
那我们找到这样的入度为0的点，我把它输出，
而且把它关联到的这些，其他的这些点，也就是它的出边，
我们都删掉。然后把它关联到的这些点呢，它的入度都减1。
然后这个点，如果是减为0了，那我们又是
进到我们这个入度为0的点，我们下次又可以选择。所以我们回到1再继续选择。
那我们就完成了这么一个拓扑排序。那我们来看一下这个算法的框架。
首先，我们把这些入度为0的点都给它放到队列里面。
然后，我们在队不空的情况下，从队首弹出一个元素。
这个元素，它关联到一些其他的点。
那我们把这些关联到的点它的入度都减1。
然后如果某一个点，它的入度被减为0了，
那我们把它放到前面，就是可以
打印出列的，入度为0的这样的一个队列表里面。
那完成这个循环以后，我们要检查，
在这个图的结点表里面有没有某一些结点，
它的这个访问标记呢，还是标记为未访问。
那这种情况就是形成了环。也就是说，
比如说，a，b，c，3个结点它形成环的话，
那它每一个结点的入度都不为0，那我们从外界
是不能够打破它这个环的。这几个结点它也不会，
输送到我们这样的一个输出的序列里面。
那我们如果，
按照这样的一个结点编号，然后我们进行深搜。大家来观察一下，它的这个结果。
那对这个有向无环图，那我们从C1出发，我深搜，
一直到这个C6的时候，C6它没有后继了。这个时候呢，我们相当于在，
它的这个后访问点，把这个C6给打印出来。
然后C4，它还有C7没访问完。那C7可以访问，然后呢，
C4，它的这个后访问点呢，也可以处理了。
C4可以出列。然后呢，我们一直这样持续地去访问。
那得到这个序列，我们把它逆置一下，大家可以观察一下。
这个序列就是一个正确的拓扑序列。
原因呢就是，我们刚才在得到这样的一个
访问的序列的时候，我们是在后访问点来打印这个结点的。
那也就是说我们所打印这个结点的时候呢，
它的这些前趋的这些先决条件一定在它后面出现。
那我把它逆置一下，那显然就是一个满足先决条件的一个拓扑序列。
那我们这样的一个深搜的实现框架呢，就是这样的。
那在进入到这个框架的时候，我们首先，
把这些所有的这个结点的标记位都置为未访问。
然后呢，我们设置一个这样的
结果序列。我们首先给它准备一些空间。
另外我们对这个结点表逐个地来，
考察。如果是这个结点它没有被访问过。那，
我们就去调用一个深搜的这么一个算法。
然后，我们这个整个深搜都处理完了以后，
我们要对这个结果表，进行一个逆置的操作，来得到一个拓扑序列。
那我们再来看一下，这个深搜的核心算法。
那这个核心算法，一开始进到这个点，我们也是给它设置为已经访问。
然后，我们把这个点涉及到的相邻的
邻接点来看一下它们这些邻接点是不是已经访问了。
如果是没有被访问呢，那我们就递归地调用这个深搜的算法。
完成这个深搜以后，也就是在这个结点
它之下的这些访问点都处理完了以后，
那我们这里，就是一个，后访问点的操作。
那我把这个结点入到这个结果的一个表里面。
那我们这样的一个框架大家
注意看一下，我们在所有的图的算法里面，
都是，这个for循环是非常重要的。
也就是我们从一个结点出发，然后去找它的邻接点的时候呢，
我们是，从它的第一条邻接边引出，然后这个for循环是，
它的一个往后推的条件呢，它就指向下一个邻接的这样的一个边。
然后一直到这个边是图里面的有效边的时候，我们一直进行。然后，
我们在这个底下的这个处理框架的时候，我们
是对这个边所引向的那个
终结点来进行相关的操作。这是图的一个典型的处理框架。
好，那我们来看一下拓扑排序的
时间复杂度。那不管是递归还是非递归的，
那我们其实跟图的这个深搜算法它的遍历是
相同的。我们每一个结点，每一条边，都是被处理而且只被处理一次。
那采用邻接表的时候呢，它就是Θ(n+e)的时间。
采用相邻矩阵呢，它就是theta n方的时间。
对于图的算法，我们需要考虑的一些问题
最关键的首先就是，它是支持的有向图还是无向图？
另外呢，它是不是支持有回路的图？是不是支持不连通的图？
还有，这个图它的权值是不是可以为负？
当然，也就是前提是它有没有权值。
如果是没有权值的话，我们就不考虑这个负权值的情况了。
另外，对前面的这些问题，我们考虑一下，怎么样去修改？
那，我们来看递归与非递归的拓扑排序，
它们有一些，什么需要考虑的？
首先呢，它是支持有向无环图。
对于连通性没有什么特殊的要求。而且拓扑排序，我根本不考虑这些边的权值的情况。
但是，有一个回路的情况，我们需要考虑。
对于这种非递归的算法，
最后要判断一下，顶点表里面的这些结点，它是不是已经都被访问到了？
如果有没被访问到的结点，那就说明存在环。
所以它不存在把这个环呢，
设为这个入度为0的这种可能性。
所以这些环中的结点呢，都不能够被访问到。
那，我们采用的后访问点的这样的深搜的框架，
它是个递归的算法。这个算法呢，它其实不能够正确地判断，
有环的这种图。那我们知道，
对于拓扑排序我们是处理的有向无环图的情况。那
有环图它也会给你打印出一个序列，告诉你这是拓扑序列，那显然是错误的。
好，那我们最后给大家留几个思考。首先就是用队列实现的拓扑排序，
我们怎么样知道这个图里面所有顶点的入度呢？
那我是不是需要先做一些预处理？还有，我们采用的是队列，
那能不能够改为栈，来实现呢？另外，对
深搜框架的拓扑排序，我们对于，
搜索的起点有没有要求？
还有就是我们能不能够处理有环的情况？
如果那个框架不能处理，你能不能够做简单的修改，使得你的算法能够处理？
谢谢大家。