——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。
图中环的检测
无向图中环的检测
基本思想：若在图的遍历过程中遇到已经访问过的顶点，则存在环。
实现方法：①图的遍历使用非递归算法，若出现将要访问的新出栈（DFS）或队列（BFS）的顶点为已经访问过的顶点，则存在环；或②图的遍历使用递归算法（DFS），若出现当前将要作为参数进行DFS()调用的顶点为已经访问过的顶点（即在DFS()的执行中遇到已经访问过的顶点），则存在环。
有向图中环的检测
基本思想：图的遍历使用递归算法（DFS），若在DFS(v)结束之前出现一条从顶点u到顶点v的回边，则必存在环（因为u在生成树上是v的子孙，现在出现子孙到祖先的回边，则必存在环）。（对于有向图，无法通过图的遍历的非递归算法（DFS或BFS）实现环的检测）
有向无环图
有向无环图可用来以公共子表达式的方式描述表达式。
对有向图的顶点适当地编号，可使其邻接矩阵为上（或下）三角形且主对角线为全0的充要条件是该图为无环图。编号规律：若使其邻接矩阵为上（下）三角形，则弧尾的编号小于（大于）弧头的编号，且按顶点的入度（出度）递增顺序依次编号。具体进行编号时，先按顶点的入度（出度）递增顺序依次编号，然后依据弧尾的编号小于（大于）弧头的编号的原则对前面的编号进行调整。（主对角线为全0表示不存在从某顶点出发并回到该顶点自身的弧。）
有向无环图是描述一项工程或系统的进行过程的有效工具。
对工程和系统，人们关心两个方面的问题：1）工程能否顺利进行（即进行拓扑排序）；2）完成工程所需的最短时间（即求解关键路径）。
拓扑排序
偏序关系：若集合X上的关系R是自反、反对称和传递的（集合X中可能存在不具有关系R的元素对），则称R是集合X上的偏序关系。
全序关系：设R是集合X上的偏序，如果对每个
必有
或
，则称R是集合X上的全序关系。（全序也可定义为“全部”的偏序）
直观地看，偏序（Partial Order）指集合中仅有部分成员之间可比较，全序指集合中全体成员之间均可比较。
拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序的操作称为拓扑排序。
对一个有向无环图(DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。
AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向图。
检测AOV-网中是否存在环的方法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环（若存在环，则环上的两顶点x,y必定同时满足xRy和yRx，与R是反对称的矛盾）。
拓扑排序的方法：
方法1：
1）在有向图中选一个没有前驱的顶点（可能是本来就没有前驱，或前驱已经全部输出且以该顶点为弧头的弧通过2）全部删除了）且输出之；
2）从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出，表示图中不存在环；或直至图中不存在无前驱的顶点为止，表示图中存在环。
方法2：
当有向图中无环时，可利用DFS遍历进行拓扑排序，因为图中无环，则由图中某点出发进行DFS遍历时，最先退出DFS函数的顶点即出度为零的顶点，是拓扑有序序列中最后一个顶点。由此，按退出DFS函数的先后顺序记录下来的顶点序列即为逆向的拓扑有序序列。
关键路径
AOE-网：顶点表示事件，弧表示活动的带权（权表示活动持续的时间）有向无环图。
AOE-网中的路径长度：路径上各活动持续的时间之和。
关键路径：AOE-网中路径长度最长的路径（关键路径长度是完成整个工程所需的最短时间）。
关键活动：最早开始时间等于最迟开始时间的活动称为关键活动（或关键路径上的活动称为关键活动）。
求AOE-网中活动的最早开始时间e(i)和最迟开始时间l(i)，首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。若活动ai由弧<j,k>表示，其持续时间记为dut(<j,k>)，则有如下关系
，
。
（在不推迟整个工程的完成的前提下，
，
，其中0为源点，
为汇点。）
（1）求事件的最早发生时间
从
开始向前递推
，
其中，T是所有以第j个顶点为头的弧的集合。
（2）求事件的最迟发生时间
从
起向后递推（
已由（1）求得）
，
其中，S是所有以第i个顶点为尾的弧的集合。
上面两个递推公式的计算必须先（1）后（2），且必须分别在拓扑有序和逆拓扑有序的前提下进行。即
必须在
的所有前驱的最早发生时间求得后才能确定，
必须在
的所有后继的最迟发生时间求得后才能确定，因此可以在拓扑排序的基础上计算
和
。
最短路径
1.从某个源点到指定顶点的最短路径
与求从某个源点到其余各顶点的最短路径相同，只是在Dijkstra算法中，当新并入最短路径顶点集的顶点为指定顶点时，便可结束。
2.从某个源点到其余各顶点的最短路径
Dijkstra算法
基本思想：按路径长度递增的次序产生最短路径。
算法原理：假设S是已求得的源点为v的最短路径的终点的集合，则下一条最短路径（设其终点为x）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点x的路径。（证明：反证法。假设下一条最短路径p上有一个顶点（除终点x外）不在S中，则说明存在一条终点不在S中而长度比p短的路径，这与按路径长度递增的次序产生最短路径相矛盾。）
算法实现：
1）在已选出的最短路径的基础上，重新找到达未并入最短路径顶点集中的每一个顶点
的最短路径（方法是取
最小的值，其中
表示路径
的长度，
表示弧
的长度，
为源点，
，
可以是
）；
2）从1）中新找到的到未并入最短路径顶点集中的每一个顶点的最短路径中选最短者，将其目的顶点并入最短路径顶点集S中。
（该算法类似求解最小生成树的Prim算法，不同点是Prim算法每次找的是代价最小的边，而Dijkstra算法每次找的是代价最小的路径。）
Dijkstra算法的时间复杂度为
。
3.每一对顶点之间的最短路径
方法1
基本思想：每次以一个顶点为源点，重复Dijkstra算法n次。
该算法的时间复杂度为
。
方法2
Floyd算法
基本思想：若
和
分别是从
到
和从
到
的中间顶点的序号不大于k-1的最短路径，则将
和已经得到的从
到
且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从到
的中间顶点序号不大于k的最短路径。当k=n时，便可求得从到
的最短路径。
Floyd算法的时间复杂度为
。（共有中间点、源点和终点三层迭代，即需按顶点序号递增的顺序依次将每一个顶点作为中间点进行其是否可能为当前任意源点和终点之间的最短路径上的序号最大的点的验证，故时间复杂度为
。）——可选择“【右上角···】→【在浏览器中打开】”进行横屏阅读。
