学了C/C++ 语言，我们已经会编程解题了，那怎么用来处理实际的问题呢？ 怎么设计数据结构来有效地管理企业人员？如何编写程序没让人才和岗位达到最佳匹配？如何安排旅行计划，找到最佳行程路径？这些学习、工作、生活中常常困扰我们的问题，你将在《数据结构基础》课程中找到答案。 数据结构是计算机程序设计的基础，告诉我们数据在计算机里是如何组织与存储的，能帮助我们刻画实际问题中的信息及其相互关系。当我们对一个实际问题本身有了一个结构化的认识之后，就可以选择合适的解决方法了。 完成这门课之时，你将掌握线性表、栈与队列、字符串、二叉树、树、图等经典的数据结构，并运用这些基础数据结构和相关算法解决实际应用问题。扎实的数据结构知识是项目开发与结构层次设计的关键，学好这门课会让你在高年级的计算机专业课程以及毕业项目设计中事半功倍，同时也将为你成为一名优秀的程序设计人员打下坚实的基础。 附：本课程的内容来自教材：《数据结构与算法》（张铭、王腾蛟、赵海燕 编著），高等教育出版社，2008年。
拓扑排序和图的路径问题
Loading...
来自 Peking University 的课程
数据结构基础
218 个评分
从本节课中
图
实际生活中可以用图的形式描述的问题随处可见，例如通信网络、社交网络等。图通常用来描述一个网状关系，图的结点描述了个体的信息，结点与结点之间的边描述了个体之间的关系，边还可以有权重，描述了这种关系的强弱程度。
在这一章中，除了图的存储结构、遍历方法，你还会学到图结构的实际应用，如最短路径和最小生成树这两类最常见、最经典问题的解决方法。
重点：图的深搜、宽搜框架；图的相邻矩阵、邻接表、十字链表等存储方法。图的最短路Dijkstra算法、Floyd算法，最小生成树Prim、Kruskal算法。
难点：基于这图搜索框架的应用，例如拓扑排序；图的不同存储方式，适应范围和时空复杂度；最短路、最小生成树等综合应用。
与讲师见面
Prof. Ming Zhang 张铭教授
School of Electronics Engineering and Computer Science北京大学计算机系
接下来我们继续图的拓扑排序相关习题课的学习。
拓扑排序的拓展问题有很多， 比如说POJ平台上的1094问题。
已知A<B, A<C, B<C,
C<D, B<D 这四个，那么A, B, C,
D的大小关系可以由前几个表达式确定呢？ 这个需要判断拓扑排序的唯一性。
首先我们来复习一下拓扑排序它的算法。
对于一个任意的有向无环图都有拓扑序列。
求拓扑序列的基本方法呢有反复删除入度为零的顶点
和后续深度周游的逆序列这两种方法。
而后续深度周游的逆序列呢， 是先对有向图进行后续的深度优先周游。
再记录深度优先周游的结点访问向量。
然后再逆序该向量，即为拓扑排序的结果。
对于右图所示的图来说，也从V0开始访问。
由V0再到V2， V2继续深度优先，V3，
继续深度优先V5，V5不再有边
到其他的结点，所以V5先输出，
其次， 到V3,
V3没有其他的出边，所以 V3也输出，
再回到V2, V2也没有其他的出边，所以V2也输出。
再回到V0，
V0继续访问V4， V4再继续访问，发现
V5已经访问过了，所以发现V4 的出边指向了已经访问过的两个结点，
所以说V4也输出，再输出V0，
最后输出V1，
所以我们得到后续深度周游的，
序列为V5，V3，V2，V4，V0，V1。
所以说相应的拓扑排序的序列就应该是V1，V0
V4，V2，V3 和V5。
针对有回路的拓扑排序，我们的解决方法是， 将标志位设为三种情况，
unvisit, visit 和pushed。
pushed表明已经放入结果数组。
当发现一个结点， 从它所邻接到的结点中，若有已标志为
visit但不是pushed的时候，表示出现了环， 所以说我们要打印存在环。
这个是针对有回路的拓扑排序，
的算法，它利用的是后续深度周游
的方法，首先对图中所有的
顶点的标志位进行初始化， 再对每一个顶点进行周游，
如果说发现， 没有周游过的结点，则继续深度周游，
如果说没有环，那就逆序输出，
刚才周游的结点，所以说
解决1094问题，我们的方法是从第一个规则进行读入，
把它加入到图中，变成图的一条边， 然后对这整个图，
进行周游，如果说有环，肯定是 不能进行拓扑排序的，则报错，如果说可以拓扑排序，
那我们就要去判断它的唯一性，
如果唯一则停止输出结果，那么唯一性怎么判断呢？
对于这样一个图来说， 它的拓扑排列可以是ABC，也可以是ACB。
肯定是拓扑排序不唯一的。
肯定是拓扑排序不唯一的。
它的特点在于，当删掉这个
A的时候，马上出现了两个 速度为0的点，所以说，
如果我们能够在这一步判断一下， 删掉A过后，它影响的只有一个结点，
那它的拓扑排序是不是就唯一了呢？比如说 在这个图中，
ABC的拓扑排序就是唯一的，因为每删掉一个结点， 出来的入度为0的结点都只有一个。
根据这个思想我们写出代码，
首先进行一个输入，把小于号变成一条边，
再把相应结点的入度给改变一下， 然后把这个多了一条新边的图，
作为一个新的图去判断一下是不是有拓扑排序的唯一性，
如果是，那就输出可以排序，如果不是 一直到小于规则已经被
读入完成，依然不能排序，那么说明整个图是不能排序的。
我们来看看判断拓扑排序唯一性的函数的代码。
其它的都和删除入度为0的结点算法， 非常类似，只是多了一点判断，
去掉入度为0的结点过后，队列是不是 只有一个原数，这段代码，其实就等于是
判断了入度为0过后，这样 我们就能够判断拓扑排序的唯一性。
接下来我们来探讨一下图中另外一个流行问题。
关键路径问题，首先来介绍一下AOE图的概念，
在日常生活中我们经常遇到， 一些建筑工程什么活动应该先做，
什么活动应该后做这样的问题。比如说在如左图所示的图中，
如果一个建筑工程中需要修围墙16天， 进材料3天，拆迁两年，打地基40天，
盖房子120天 那么，盖房子肯定必须在最后完成。
其他的修围墙和拆迁， 进材料和打地基，是可以并行进行的。我们把
左边这样一个图画成右边的AOE图。
在这里，a1代表的是修围墙，a2代表的是拆迁， 依次类推，而v1，v2，v3，v4只是一个时间结点，
它只是为了标志这个事件发生的并行性而存在的。
那么我们研究什么样的问题呢？
完成整项工程至少需要多少时间？哪些活动是影响整个工程进度的关键？
注意，我们在求关键路径的时候，肯定是在拓扑排序的前提下进行的。
如果不能进行拓扑排序，自然也不能求关键路径。
完成整个工程的最短时间， 是从开始顶点到完成顶点的最长路径的长度。
为什么不是最短路径呢？因为 在这里，修围墙16天，进材料3天，
其实总共只用了19天，而拆迁两年， 和打地基40天，这里面用了两年多的时间，
所以说，拆迁这条路，也就是v1，v2，v4这条路。
它需要等v1，v3，v4这条路将近两年多的时间。
但是这个时间是没办法省的，因为你要盖房子的话，必须要拆迁完毕，并且打地基完毕。
所以说，我们在这里完成整个工程的最短时间必须是最长路径的长度。
路径长度为路径上各边全值的合。
把开始结点到完成结点最长路径我们称之为关键路径。
关键路径上的活动可以决定整个工程
是否能够提前完成。
要解决关键路径的问题，我们先来定义一下v1j 即事件可能发生的最早时刻。
代表了从vj出发的所有活动最早开始的时间。
e代表earning，vl(i)代表在保证
不延误整个工期的前提下，时间vi所允许发生的最晚时刻。
活动ak等于 <vi,vj>它的最早开始时间
是e(k)。活动ak 它最晚开始时间为l(k)，l是late的意思。
l(k)- e(k)表示完成活动 的时间余量，是指在不延误工期的前提下
活动a(k)可以延迟的时间，所以 当e(k)
= l(k)的时候，说明这个活动 没有活动时间，没有延迟时间，它就是一个关键活动。
那么我们怎么去求关键活动呢？ 怎么去求l(k)
e(k)呢？选一个例子来说， 在这样一个复杂的工程图里面，
V5要依赖V2 V3的完成， V8 要依赖V5
V6的完成，V7要 依赖V5的完成，V9要依赖V7 V8的完成。
首先，V1的最早开始时间是零。
其次V2的最早开始时间是6。
因为a1需要六个时间点 才能完成。V3的时间点是4。
V4的最早开始时间是5，以此类推。
V5是7，从V1 V2到V5
需要七个时间点，从V1 V3到V5
需要五个时间点，而V5必须在V2V3都完成的情况下 进行。所以说它的最早发生时刻是7。
接下来，V6是7，V7最早 的开始时间是16，V8是14，V9是18。
所以在不延误工期的情况下 V9的最晚发生时间是18，V8
是14，V7是16。
V6是10，对于V5来说 如果要保证V7准点开始进行，
需要开始的时间是7，如果要保证V8开始的话，
它的时间也是7，所以它的最晚发生时刻是7。
V4发生时间是8，V3
V2，对于V1 是零，所以我们求出了每个节点的最晚发生时间
和最早发生时间。接下来，对于每一个
活动来说，它的最晚发生时间和最早发生时间也已经决定了
求出了事件的最晚和最早发生时间 我们响应的可以求出活动的最晚和最早发生时间。
最终就可以看出 哪一些是关键活动。在这里面我们可以看到
活动1，活动4，活动7， 活动10和活动11，它们的
e(i)和l(i)是相等的，所以它们是关键活动。
我们来总结一下关键路径的算法。
首先输入e条弧，建立图的存储结构，再从节点V0开始。
令ve为零，求ve(j)， 再反过来，从Vn-1出发。
令vl(n-1) = ve(n-1)，求vl(i)，
最后根据各顶点的ve和vl值 求每条弧ak的最早发生时间。
e(k) = ve(i)和最晚开始时间l(k) =
vl(j)减去 <vi,vj>这条边的全总。
最后e(k)=l(k)的就是关键活动了。
接下拉我们进行图的最短路径的复习，图的最短路径iii也非常的多。
例如POJ平台的1376问题， 直径为1.6的圆形机器人如何能避过障碍，
以最短的时间从起点到达终点？
这个机器人它可以移动以格，或者是左传90度，或者是右转90度。
这些都需要一个单位的时间，如果我们能够给出起点和终点的坐标
和初始方向，需要求这个机器人怎么才能够尽快地达到终点。
这个问题的本质其实是可达点的最短路径。
我们可以把每一个坐标都看成一个节点。
两个节点之间如果有障碍物，代表它们两个之间没有边。
如果有障碍物，它们两个之间没有边。
我们要求的就是 给定起点和终点，求这两个之间最短路径
的问题。那376的问题的输入，第一行 9，代表有九行。
10，代表有10列。这标定了整个图的 大小。而接下来
一共有9x10个数字，分别代表着这个图里面是否有障碍。
最后，72和27分别代表起点和终点 的坐标，south代表了起点的时候机器人的面对方向。
如果输入是两个零，就代表输入结束。
输出代表需要的输出式最短路径的长度，
也就是机器人需要的时间。我们来看
具体算法。首先， 输入整个图中障碍物的情况。
其次，用一个iii来标志整个图中我们是否
周游过某一个节点，再对整个图进行广度优先的周游。
如果整个图中，某个方向没有障碍物，那我们就向这个方向
前进一步，并且把这条路径的长度记录下来。
这样我们尝试了所有的路径过后 就能够得到一条最短的路径。
谢谢您听！
