《算法与数据结构考研试题精析》笔记(7) - 图
基本概念及性质
【简单路径】如果路径上的各顶点均不互相重复，称这样的路径为简单路径。如果路径上的第一个顶点与最后一个顶点重合，这样的路径称为回路(cycle)或环或圈。
【连通分量】无向图的连通分量指无向图中的极大连通子图。
【强连通】一个有向图中任意两点v1、v2间存在v1到v2的路径及v2到v1的路径。
【错误说法】图的遍历就是图中某一顶点出发访遍图中其余顶点。
错误原因：没有强调次数。图的遍历为“对各顶点遍历一次且仅一次”。
【错误说法】任何一个关键活动提前完成，那么整个工程将会提前完成。
PS：一个工程的关键路径不一定只有一条。如果某一关键活动不是某一关键路径上的活动，而属于另一条关键路径，则完成此关键活动，显然不能使得整个工程提前完成。
【正确说法】在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。
因为关键路径是从源点到汇点的最长路径，如果关键路径上时间延长了，那么整个工程所需要的时间也就延长了。
【错误说法】若有向图不存在回路，即使不用访问标志位，同一结点也不会被访问两次。
深度优先遍历的时候，回溯的时候，有的结点会被访问两次(尽管有向图中并不存在回路)。
在有向图中，出度为0的结点称为叶子。
- 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同。
- 一个事件的最迟开始时间，是该事件所有后继事件(顶点)最迟开始时间和相应活动持续时间差的最小值。
注意“弧头”和“弧尾”的定义为何，莫弄混淆了。
- AOV网中，结点表示活动，边表示活动的优先关系。
- AOE网中，结点表示事件，边表示活动，边上的权表示活动持续事件。
在AOV网中，存在环意味着某项活动以自己为先决条件，这是荒谬的；对程序的数据流程图来说，它表示存在着死循环。
图中的边和点
无向图中，边的数量n与各结点度数d_i之间的关系：
如此理解：每一条边两头都杵着两个点
若一个具有n个顶点、e条边的无向图是一个森林，则该森林中必有n-e课树。
【最少边数】
- 一个
n个顶点的连通无向图，其边的个数至少为n-1; - 一个
n个顶点的连通有向图，其边的个数至少为n; - 【推广】N个顶点的连通图用邻接矩阵表示时，该矩阵至少有
2(N-1)个非零元素。
对于N个顶点的有向图而言，最少的边数为
N，则此时的邻接矩阵有2N个非零元素； 对于N个顶点的无向图而言，最少的边数为N-1，则此时的邻接矩阵有2(N-1)个非零元素; 故而，矩阵至少有2(N-1)个非零元素。
【完全图的边数】
- 一个
n的顶点的有向完全图有n(n-1)条边； - 一个
n的顶点的无向完全图有n(n-1)/2条边。
【确保为连通图的边数】
具有n个顶点的无向图，当有(n-1)(n-2)/2+1条边时，能确保是一个连通图。
关于时空复杂度
时间
- 对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法复杂度为
O(n+e)； 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为O(n+e)。
Prim算法的时间复杂度为O(n^2)(n为结点的频度)，与网中的边数无关，因此适用于求边稠密的网的最小生成树；而Kruscal算法的时间复杂度为O(eloge)(e为网中边的数目)，因此它相对于Prim算法来说，更适合于边稀疏的网的最小生成树。
对于Prim算法而言，如果图采用邻接矩阵的存储方式，则时间复杂度为
O(n^2)；如果采取邻接表的存储方式，则时间复杂度为O(n+e)。
- 用邻接矩阵表示时，Dijkstra算法的时间复杂度为
O(|V|^2)，Floyd算法的时间复杂度为O(|V|^3)； - 在用邻接表表示图时，拓扑排序的算法的时间复杂度为
O(n+e)；
遍历图的过程实质上是查找顶点邻接点的过程，BFS遍历图的时间复杂度为O(n+e)，DFS遍历图的时间复杂度为O(n+e)，两者不同之处在于访问顶点的顺序不同，反映在数据结构上的差别是栈和队列。
设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为O(n+e)。
空间
用邻接表存储图所用的空间大小与图的顶点数和边数都有关。
拓扑序列
若用邻接矩阵存储有向图，矩阵中主对角元素以下的元素均为零，则该图拓扑序列存在但可能不唯一。
对于一个有向图而言，我们分如下情况考虑其邻接矩阵。
- 若是下三角矩阵，说明编号大的顶点是弧尾，编号小的是弧头，不会出现编号小的顶点指向编号大的现象。
- 若是上三角矩阵，则与上三角矩阵的情况完全相反。
- 上述两种情况说明该有向图可以拓扑排序，但是具有拓扑排序序列的有向图的邻接矩阵不一定是三角矩阵。
有向无环图具有拓扑排序序列，其邻接矩阵没有明显特征。
【错误说法】在拓扑序列中，任意两个结点相继结点Vi和Vj都存在从Vi到Vj的路径。
错误原因：在拓扑排序的算法中，在某一时间点，可能会出现存在一个以上的点入度为零，此时的这两点之间，就不存在一点到另一点的路径(因为同时入度为零，则两者在拓扑序列中，可选任意一者在前，这对前述无影响)。
在拓扑分类中，拓扑序列的最后一个顶点必定是出度为零的。
拓扑分类就是拓扑排序
最小生成树
最小支撑树就是最小生成树。
最小生成树的代价就是最小生成树各边权值之和。
如果连通图上各边权值均不相同，则该图的最小生成树是唯一的。
最小生成树的Kruscal算法和Prim算法都是贪心算法。
应用
可以判断有向图是否有回路(有环)的方法：深度优先遍历、拓扑排序。