Chapter 6. 图
概念
-
带权无向图
G中，若所有边的权值都不相同，则G的最小生成树是唯一的。不论
Prim算法还是Kruskal算法，都优先选择（全局或点集的）最小边，若没有同权边，则最小生成树必定相同。 -
十字链表 邻接多重表 适用于 有向图 无向图 -
稀疏图与稠密图的区别中，点与边的大小关系是相对而言的。主流说法认为当 |E| \le |V| \log _ 2 |V| 时为稀疏图，当 |E| \gt |V| \log _ 2 |V| 时为稠密图。
-
邻接矩阵存储的有向无环图若存在拓扑序列则其拓扑序列唯一。
邻接矩阵的按顺序遍历得到的拓扑序列顺序是固定的。
-
Prim算法Kruskal算法适合 稠密图 稀疏图 邻接矩阵时间复杂度 O(n^2) （与边数无关） O(e \log _2 e) （与边数有关） 邻接表时间复杂度 O(n+e) O(e \log _2 e) （时间开销主要在对边权值的排序上） -
逆邻接表：表头为入结点。
考点
-
具有 20 个顶点和 25 条边的无向图的连通分量最多为 13 。
选择将所有边放在一个连通分量内，而不是尽量用边填满每个连通分量。
由于 \frac {7 \times (7-1)} {2} \lt 25 < \frac {8 \times (8-1) } {2} ， 25 条边至少需要 8 个顶点来连接，剩下 12 个顶点各自组成一个连通分量，总连通分量最多为 1+12=13 。 -
从 n 个顶点的连通图中选取 n-1 条权值最小的边不能构成最小生成树。
选取的边可能构成环或根本不连通。
-
图的最小生成树代价唯一。
生成树上各边的权值之和称为该生成树的代价。
-
设有向图
G的邻接矩阵是矩阵 A ，则 A^k [i][j]=m 表示从顶点i到顶点j有 m 条长度为 k 的边。 -
若无向图
G有 n 个顶点，其邻接矩阵为 A[1 \cdots n][1 \cdots n] ，且压缩存储在 B[1 \cdots k] ，则 k 的值至少为 \frac {n(n-1)} {2} 。简单图不存在自环，故无需存储对角线的值。
-
对于一个非连通无向图
G，采用深度优先遍历访问所有顶点，在DFSTraverse函数中调用DFS的次数等于连通分量数。注意是在
DFSTraverse函数中调用的次数。DFS每次递归结束代表遍历完一个连通分量。 -
具有 n 个顶点和 e 条边的图的深度优先搜索算法的时间复杂度为 O(n^2) 。
采用邻接矩阵时为 O(n^2) ，采用邻接表时为 O(n+e) ，综上时间复杂度为 O(n^2) 。
-
有向图即使不存在回路，也必须用访问标志位，否则同一结点可能被访问两次。
-
一个图的广度优先生成树的形态不唯一
与邻接表不唯一等价。
-
使用深度优先遍历算法递归地遍历一个无环有向图，并在退出递归时输出相应顶点 ，这样得到的顶点序列逆拓扑有序。
输出的顶点序列不只一种，但都是逆拓扑有序。
-
权值最小的边不一定会出现在所有的最小生成树中。
最小边可能构成环。
-
用有向无环图描述表达式 (x+y)((x+y)/x) ，需要的顶点个数至少是 5 。
结点分别为 x,y,+,\times,\div 。
-
即使有向图的拓扑有序序列唯一，也不能得到图中每个顶点的入度和出度唯一。
-
若有向图具有有序的拓扑排序序列，则他的邻接矩阵必定为三角形。（拓扑无序表示未按照结点之间依赖关系排序）
-
若邻接矩阵存储有向图，矩阵中主对角线以下元素均为 0 ，则该图的拓扑序列存在；在此基础上若主对角线以上均为 1 ，则拓扑序列一定唯一。
-
算法 邻接矩阵 邻接表 拓扑排序 O(n^2) O(n+e) Prim算法O(n^2) O(n+e) Kruskal算法O(e \log _2 e) O(e \log _ 2 e) DFSO(n^2) O(n+e) BFSO(n^2) O(n+e) Dijkstra算法O(n^2) O(e \log _ 2 n) （需配合优先队列） Floyd算法O(n^3) O(n^3+e) -
可以判断图中是否存在回路的算法：
DFS，BFS，拓扑排序，并查集。 -
Dijkstra不能判环也不能适用于负权边。 -
关键路径上的所有活动都是关键活动，但加快某个关键活动不一定能缩短整个工期；但关键活动时间延长多少，整个工期也就随之延长多少。