Relax1000 数据结构 · 第6章 图 · 解析¶
第6章 图¶
本章 65 题；解析册印刷页 41–51。
速对答案（原书）： B A D D C C B D D C A B C A B A B C C B A C C D D B A D C C C A A D A B D C C A B C A A D D C C A C A D D D C B D A A A C D C A D
Q1¶
速对表原值： B
详细解析标注： B
边数 * 2 = 度数总和。答案为(164+23+52+41)/2=42。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q2¶
速对表原值： A
详细解析标注： A
选项 B、D 均为生成树的特点，而选项 A 为概念错误：生成树 G'为最小连通子图而非连通分量（最大连通子图），本题答案为 A。
Q3¶
速对表原值： D
详细解析标注： D
A 错误。根据强连通分量的定义，u 与 v 之间互相存在路径，u' 与 v' 之间互相存在路径。若图 G 存在一条从点 v' 到点 v 的路径 〔公式/符号见原页版面片段〕' → 〔公式/符号见原页版面片段〕，则 G 也将包含路径 (〔公式/符号见原页版面片段〕 → 〔公式/符号见原页版面片段〕' → 〔公式/符号见原页版面片段〕') 和。如此就会有 u 和 v' 相互可以到达，从而与 c 和 c' 是不同的强连通分量的假设矛盾。
B 错误，若在图G 中加入一条新边，若该边的两个顶点都处于同一个连通分量，则不会生成 G 的新的一个连通分量。
C 错误。理由见 D。
D 正确，若在图 G 中加入一条新边，若该边的两个顶点 A 和 A' 分别处于不同的连通分量，并且 A 和 A' 之间原先有一条路径，假设该路径简化后表示成 A->mids->A'(同理也可假设A-mids->A)，若添加一条边生成路径 A'->A，形成一个环路，就会生成 A 和 A' 间的新的一个强连通分量，就会使得 G 的连通分量的个数加 1。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q4¶
速对表原值： D
详细解析标注： D
若一个无向图有 n 个顶点和 n-1 条边，可以使它连通但没有环(即生成树)，但若再加一条边，在不考虑重边的情形下，则必然会构成环。
Q5¶
速对表原值： C
详细解析标注： C
A错误。强连通分量内的任意两个元素都存在到彼此的路径。不同强连通分量的顶点可以只有单向的边。如下图。
B 错误。u→v 的直接边被删除，但是可能仍然存在 u→v 的路径，比如下图，1→3 被删除后，仍然是一个强连通分量（环）。
C 正确。如果存在 u→u'的路径，那么强连通分量 c 的任意顶点可以通过 u→u'的路径到达强连通分量 c'的任意顶点。如果存在
D 错误。添加后，强连通分量可能合并，导致减少。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q6¶
速对表原值： C
详细解析标注： C
考查至少有多少个顶点的情形，我们考虑该非连通图最极端的情况，即它由一个完全图加一个独立的顶点构成，此时若再加一条边，则必然使图变成连通图。在 28=n(n-1)/2= 8x7/2 条边的完全无向图中，总共有 8 个顶点，再加上 1 个不连通的顶点，共 9 个顶点。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q7¶
速对表原值： B
详细解析标注： B
6 个顶点的完全有向图边数是 2〔公式/符号见原页版面片段〕6 2 = 30，所以 31 条弧的强连通有向图至少有 7 个顶点。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q8¶
速对表原值： D
详细解析标注： D
这题是根据真题改编，真题是无向图，要满足任意情况下所有结点都是联通的，那么 n 个结点中 n-1 个结点尽可能的多浪费边，即 n-1 个结点构成完全无向图，边数为〔公式/符号见原页版面片段〕−1 2，最后一个结点再用一条边连接，这样能保证任意情况下都能连通，公式是 1 + 〔公式/符号见原页版面片段〕−1 2。而这道题，要保证任意性，同样 n-1 个结点要保证多浪费尽可能多的边数，也就是完全有向图，这时候边数是 2〔公式/符号见原页版面片段〕−1 2。最后一个顶点向 n-1 个顶点各发出一条出边，这样保证了 n-1 个结点是强连通的，而最后一个顶点不连通，此时任加一条边，都会构成强连通图。经以上分析，可以得到公式：〔公式/符号见原页版面片段〕 + 2〔公式/符号见原页版面片段〕−1 2，n=4 时答案为 10，即选 D。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q9¶
速对表原值： D
详细解析标注： D
k > 1，说明整个图不连通，不连通的情况下最大边数是 〔公式/符号见原页版面片段〕 − 1 2，解析见上题。A、B 反例：如果 k=n，也就是每个节点都是一个强连通分量，那么边数 m=0，所以 m 最小值是 n-k。
注意：如果 k<n，那么 B 是正确的，因为 k 个强连通分量，那么让 k-1 个结点为单结点强连通分量，剩余 n-k+1 个结点为剩余的一个强连通分量，n-k+1 个结点至少有 n-k+1 条边。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q10¶
速对表原值： C
详细解析标注： C
初始考虑只有 51 个顶点的无向图 G，此时 G 中每个顶点都是连通分量，问题转化为向 G 中添加 21 条边，如何添加这 21 条边使得连通分量数目最多。若向两个不同的连通分量之间添加边，则连通分量数目会减 1，所以应尽可能地将这 21 条边加入同一个连通分量且让其接近完全图，含有 7 个顶点的完全图有 21 条边，所以用 7 个顶点构成一个含有 21 条边的连通分量，剩下 51-7=44 个顶点对应 44 个连通分量，共有 45 个连通分量。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q11¶
速对表原值： A
详细解析标注： A
A 错误，强连通的有向图的任何顶点到其他顶点都有路径，而非弧。
Q12¶
速对表原值： B
详细解析标注： B
n 个顶点的生成树是具有 n-1 条边的极小连通子图，因为 n 个顶点构成的环共有 n条边，去掉任意一条边就是一棵生成树，所以共有 n 种情况，所以可以有 n 棵不同的生成树。
Q13¶
速对表原值： C
详细解析标注： C
在树中出了根节点（没有父亲结点），其他每个结点对应一条边，所以多出的来边即根节点的个数，根节点的个数即树的棵树，一共 n-e 棵，答案选 C。
Q14¶
速对表原值： A
详细解析标注： A
选项 A 错误。当且仅当有向图中每个强连通分量顶点数都大于 1 个，才满足m≥n。反例：只要取一个连通分量顶点只有一个，就不满足结论。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q15¶
速对表原值： B
详细解析标注： B
强连通分量是极大强连通子图，任意两个顶点之间有方向相反的两条路径。由定义不难得出，若一个顶点只有出边或入边，则该顶点必定单独构成一个连通分量。图中，顶点 B 只有出边，其他所有顶点都不可能有到顶点 B 的路径，所以顶点 B 单独构成一个强连通分量。在顶点 A、C、D、E 中，任意两个顶点之间都有方向相反的两条路径，所以可构成一个强连通分量。
Q16¶
速对表原值： A
详细解析标注： A
I 错误，任意无向图的生成森林中顶点数量=边数+连通分量数II 正确.在一个连通无向图中，顶点数为 n，边数为 m，则它的生成树的边数为 n-1。III 错误.对于有向无环图，拓扑排序可以得到一个线性次序，但不能直接判断两个顶点之间是否有路径。IV 正确，强连通的定义是从任意一个顶点出发，都可以到达其他所有顶点。对于无向图，连通性即意味着强连通性。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q17¶
速对表原值： B
详细解析标注： B
为了使顶点数最少，我们需要构成一个完全连通图和一个单独点的子图，所以设有 10 条边的完全连通图的顶点数为 n，则 n(n-1)/2=10，可以求出 n=5，即该图的顶点数至少有 5+1=6个。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q18¶
速对表原值： C
详细解析标注： C
A 错误，邻接表找寻有向图某指定弧比如
B 错误，无向图没有入度和出度的概念，无向图的度就是与之相连的所有边，遍历对应邻接矩阵中的行/列，无需都遍历。
C 正确，无向图的表示中，邻接表每条边在边表中对应 2 个结点，所以结点总数有 2e 个（e 是边数），邻接多重表中边表结点只有 e 个，但每条边对应的边表结点都被其两个端点关联，这种关联在邻接多重表中体现在指针上，要么是某个顶点上一条关联边的指针指向该条关联边，要么是顶点表的指针指向该关联边，总体指针数量是 2e。
D 错误，前半句正确后半句错误，十字链表法统计入度和出度都很方便。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q19¶
速对表原值： C
详细解析标注： C
本题考查深度优先遍历。深度优先遍历是找到新的访问结点后，就从新结点开始找新的访问结点，如果没有找到，那么回溯到上一个找到的新的访问结点继续查找。从顶点 1 出发，下一个新访问结点 3，从 3 开始，找到 4，从 4 开始，没有新结点，回溯到 3，找到新访问结点 5，从 5 开始，找到 2，从 2 开始没有新结点，回溯到 5，没有新结点，回溯到 3，没有新节结，回溯到 1，没有新结点，访问结束。所以得到的顶点序列为 1, 3, 4, 5, 2。注：当一个图只给了相应的图形时，那么它采用哪种遍历方式，遍历序列一般都是不唯一的，但是在给定了存储结构(邻接矩阵或邻接表等)时，一般相应的遍历序列都是唯一的。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q20¶
速对表原值： B
详细解析标注： B
从邻接矩阵中删除一个顶点，需要删除对应的行和列，时间复杂度为 O(N)，其中N 是顶点的个数，因此 A 选项错误。
B 正确，有向图中的边有一个起点和一个终点，因此每条边会使起点的出度加 1 和终点的入度加 1，所以入度和出度之和等于边数的两倍。
C 错误，子图的概念是顶点属于原图的顶点子集，边也是原图的子集，且所有边子集中的边对应的两端顶点也属于子图。强连通分量内的子图可能是不连通的。
D 错误，拓扑排序的结果可能并不唯一。具体来说，当有向无环图中存在多个入度为 0 的顶点时，可以从这些顶点中任选一个进行排序，这导致拓扑排序的结果有多种可能。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q21¶
速对表原值： A
详细解析标注： A
计算顶点 i 的入度，要遍历第 i 列非 0 元素个数。由邻接矩阵可以知道，各顶点入度依次是 1, 2, 1, 2。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q22¶
速对表原值： C
详细解析标注： C
该邻接多重表表示的无向图如下图所示，可知 C 选项的序列是深度优先遍历。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q23¶
速对表原值： C
详细解析标注： C
n个点连通且无环的简单无向图为连通图，连通则至少有n-1条边，无环则只有n-1 条边。n 个点连通且无环的简单无向图有 n-1 条边，非零个数为 2(n-1)，零元素个数为 n^2-2(n-1)。得出零元素个数为 n²-2n+2。
Q24¶
速对表原值： D
详细解析标注： D
带权有向图的邻接矩阵中，元素 0 和∞表示的都不是有向边，而入度是由邻接矩阵的列中元素个数计算出来的。本题答案为 D。（请回顾拓扑排序算法实现过程）
原页版面片段（用于核对图表、公式、矩阵或代码）
Q25¶
速对表原值： D
详细解析标注： D
D 错误。下三角矩阵说明编号大的顶点是弧尾，编号小的顶点是弧头，不会出现编号小的顶点指向编号大的顶点的情形，此时说明该有向图拥有拓扑排序，但拥有拓扑排序序列的有向图的邻接矩阵不一定是三角矩阵，有向无环图具有拓扑排序序列，其邻接矩阵没有明显的特征。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q26¶
速对表原值： B
详细解析标注： B
邻接矩阵只跟图的顶点有关，邻接表既和顶点有关也和边有关。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q27¶
速对表原值： A
详细解析标注： A
对于连通图而言，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点；对于非连通图而言，从某个顶点出发，进行一次深度优先或广度优先搜索，只能访问连通分量内的每个顶点，若要访问图的所有顶点，还需从余下的连通分量中选择一顶点出发进行遍历。
Q28¶
速对表原值： D
详细解析标注： D
要求生成树中不能有回路。
Q29¶
速对表原值： C
详细解析标注： C
先转换为邻接矩阵 A，A²[2][4]即所求答案。〔公式/符号见原页版面片段〕 =0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 0 , 〔公式/符号见原页版面片段〕2 =3 2 2 2 1 2 4 2 3 1 2 2 3 2 2 2 3 2 4 1 1 1 2 1 2 , 〔公式/符号见原页版面片段〕2 2 4 = 3
原页版面片段（用于核对图表、公式、矩阵或代码）
Q30¶
速对表原值： C
详细解析标注： C
表示的有向图如下图所示，入度为 2 的顶点有 A，B，C 三个。也可不同画出原图。只需要从顶点表每个橙色格子出发，一直沿着橙色格子继续遍历到橙色格子为^的边表结点为止，图中经过的结点数量为 2 即为入度为 2，即 A、B、C 三个顶点。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q31¶
速对表原值： C
详细解析标注： C
因为是深度优先，找到与顶点 0 直接相连的结点，由邻接矩阵知道是顶点 1（多个相邻节点取第一个找到的未遍历到的结点），然后再在邻接矩阵中找与顶点 1 直接相连的结点，得到顶点 3.相同方法找到后续结点为：顶点 4，顶点 2.因为顶点 2 的相连结点都已被遍历，所以退回到顶点4 继续遍历，遍历到顶点 5，然后是顶点 6。顺序为 ：0 1 3 4 2 5 6。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q32¶
速对表原值： A
详细解析标注： A
广度优先搜索以起始结点为中心，一层一层地向外层扩展遍历图的顶点，因此无法考虑到边权值，只适合求边权值相等的图的单源最短路径。广度优先搜索相当于树的层序遍历，选项Ⅲ错误。广度优先搜索需要用到队列，深度优先搜索需要用到栈，选项 IV 正确。
Q33¶
速对表原值： A
详细解析标注： A
I 错误，无向图的深度优先遍历中，DFS 的调用次数是连通分量的个数。在有向图中并不满足，比如“1→2”。从顶点 1 开始，这个图只调用了一次 DFS，但是强连通分量有两个，分别是 1，2。II 正确，回边表示当前调用的 dfs 过程中，正在访问的结点的边 u，有一条边
原页版面片段（用于核对图表、公式、矩阵或代码）
Q34¶
速对表原值： D
详细解析标注： D
D。【解析】该有向图如下图所示，可能的深度优先遍历序列有 12543 12534 12354 14235 14253
原页版面片段（用于核对图表、公式、矩阵或代码）
Q35¶
速对表原值： A
详细解析标注： A
U= {1, 2, 3}，V- U={4, 5, …}，候选边只能是这两个顶点集之间的边，只有 A 符合题意。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q36¶
速对表原值： B
详细解析标注： B
如下图所示
注意：答案 A 是 kruskal 算法的结果，可自己验证一下。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q37¶
速对表原值： D
详细解析标注： D
当前选取的顶点集合为{1,3,4}，Prim 只能从已选取的顶点集合出发，选取其他顶点。Kruskal 算法按照边权从小到大依次考察边，若加入该边不会形成回路，则选取该边。本题A 选项1,4 顶点已经在一个集合，所以Prim算法和Kruskal都不可能选取。B选项Kruskal算法和Prim算法都可能选；C选项因为权值2<3，(2,5)2不可能后于(3,4)3 选取，只可能是Prim算法选取。只有D 选项符合。
Q38¶
速对表原值： C
详细解析标注： C
C 错误，若图的所有边的权重都是正数，则任一连接所有结点且总权重最小的一个边集合必然形成一棵树。因为假设边子集 T 中存在环，则某两点间存在多条通路，移除其中一条通路可得子集T‘，T’仍连通所有点。因边的权重为正，有w(A')<w(A)，结论与条件矛盾，所以T必定为树。若边的权重准许为负，则子集 T 不一定就是树，例如：如下图所示的图中三条边的总权重最小。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q39¶
速对表原值： C
详细解析标注： C
I 错误，Prim 每一轮选取的是离当前生成树距离最近的顶点。II 正确，不使用堆优化的 Prim 算法，无论是邻接矩阵还是邻接表存储，都是〔公式/符号见原页版面片段〕2。使用堆优化更新 dist 数组的开销，算法步骤如下：
-
初始把<起点，0>插入堆中，第二项是 dist 值。
-
出堆直到取到未被访问过的顶点 i （visited 数组实现），然后遍历该顶点的邻边〔公式/符号见原页版面片段〕，直接向堆中插入< 〔公式/符号见原页版面片段〕, 〔公式/符号见原页版面片段〕 >
-
继续第二步，直到选取出所有顶点(堆空即可)由于堆中会有顶点重复的边，每次出堆是惰性删除已经被访问过的顶点的数据，所以最多访问 E次，每次出堆或者入堆的时间开销是〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 ，所以整体复杂度是〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 III 错误，稠密图是〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕2，所以临接矩阵存储下，时间复杂度是〔公式/符号见原页版面片段〕2 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 ，因为〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕2，所以〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 ≈ 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 > 〔公式/符号见原页版面片段〕2，所以时间复杂度是〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕。
注意：在稀疏图下，〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕 ，邻接矩阵存储下，Kruskal 算法时间复杂度为〔公式/符号见原页版面片段〕2。IV 正确，Kruskal 算法需要并查集来判断选取的边是否属于同一个集合，以及合并集合操作，所以要使用并查集。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q40¶
速对表原值： A
详细解析标注： A
A 正确，见严蔚敏撰写的教材《数据结构》。Diikstra 算法适合求解有回路的带权图的最短路径，也可以求任意两个顶点的最短路径，不适合求带负权值的最短路径问题。在用 Floyd算法求两个顶点的最短路径时，当最短路径发生更改时，〔公式/符号见原页版面片段〕ℎ〔公式/符号见原页版面片段〕−1就不是〔公式/符号见原页版面片段〕ℎ〔公式/符号见原页版面片段〕的子集。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q41¶
速对表原值： B
详细解析标注： B
A 错误，Dijkstra 算法不能求上图的结点 1 单源最短路径，从结点 1 出发，先选择结点 2，最短路径长度确定为 6，然后选择结点 3，最短路径长度为 7。说明了 Dijkstra 算法不能求解带负权图的单源最短路路径。
B 正确，Prim 算法
①从结点 1 出发，结点 1 的相关边的权值为 6、7，所以优先选 6，即结点 2 加入。
②以 1，2 作为一个整体，找出离这个整体的最短路径连接的未处理的结点，-3 是所有的边中最短的，所以结点 3 加入，至此所有结点都已在生成树里面，B 正确。
C 错误，更新的策略并不一致，这也是 Prim 和 Dijkstra 的区别，设当前选定的结点为 cur，图的边权用 w 数组存储，要更新的未处理的结点为 i，〔公式/符号见原页版面片段〕算法：〔公式/符号见原页版面片段〕ℎ 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕ℎ 〔公式/符号见原页版面片段〕算法：〔公式/符号见原页版面片段〕ℎ 〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕ℎ 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕ℎ 〔公式/符号见原页版面片段〕注：Prim 是以整个集合为源，Dijkstra 是以单个结点如本题的结点 0 为源，需要加上 path[cur]来存放 0→cur 的最短路径长度信息。
D 错误，这是最后一轮计算得到矩阵〔公式/符号见原页版面片段〕2。因为唯一会更新的是 A[1][2] =A[1][3]+A[3][2]，以结点3 为中间结点，那就是在第三轮计算得到的。通过本题，希望大家去复习和整理最小生成树，最短路径算法的相关考点，对照代码去理解算法的思想，真题考到了不至于整个空着。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q42¶
速对表原值： C
详细解析标注： C
在负权图中，Diikstra 算法既不能保证每次选出的顶点都是真正的最近顶点，又不能保证已确定的最短路径不再被改变，因此 Diikstra 算法不允许边的权为负，Ⅰ正确。求每对顶点间的最短路径需要调用 Dikstra 算法 n 次，时间复杂度为 〔公式/符号见原页版面片段〕3，Ⅱ错误。Floyd 算法求每对顶点间的最短路径允许有负边存在，但不允许有包含负边组成的回路，Ⅲ正确。
原页版面片段（用于核对图表、公式、矩阵或代码）
审计旁注（非原文）：改答案为 B
Ⅰ正确；Ⅱ错，邻接矩阵实现的 Dijkstra 运行 n 次是 O(n³)；Ⅲ把“负权回路”误写成“含负边的回路”，后者不一定是负权回路。因此仅Ⅰ正确，选 B。王道回源：result.md [block: b_242_8, b_244_0, b_244_1]。
Q43¶
速对表原值： A
详细解析标注： A
：见下图
原页版面片段（用于核对图表、公式、矩阵或代码）
Q44¶
速对表原值： A
详细解析标注： A
符合条件的有：DFS、BFS、拓扑排序。Prim算法和Dijsktra 在不使用堆优化下时间复杂度为 O(v2)，优化后是 O(elog2v)。Kruskal 算法主要开销在对边的排序算法中，时间复杂度为O(elog2e)。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q45¶
速对表原值： D
详细解析标注： D
A、B、C、D 分别对应A−1、A2、A0、A1。
Q46¶
速对表原值： D
详细解析标注： D
D 正确，对于选择题，简单的有向图可以通过手算以快速得到 Floyd 算法的结果，若通过课本上给出的标准解法则比较浪费时间。
Q47¶
速对表原值： C
详细解析标注： C
I 错误，Dijkstra 算法不能求带负权图的单源最短路径，反例如下II、III 正确。IV 错误，求每对顶点的最短路径，应该是〔公式/符号见原页版面片段〕3。时间复杂度总结如下：
原页版面片段（用于核对图表、公式、矩阵或代码）
Q48¶
速对表原值： C
详细解析标注： C
本图的拓扑排序序列有 ABCFDEG，ABCDFEG，ABCDEFG，ABDCFEG 和ABDCEFG。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q49¶
速对表原值： A
详细解析标注： A
有向图如图。拓扑排序：
①从 AOV 网中选择一个没有前驱(入度为 0)的顶点并输出
② 从网中删除该顶点和所有以它为起点的有向边
③ 重复
①和
② 直到当前的 AOV 网为空
原页版面片段（用于核对图表、公式、矩阵或代码）
Q50¶
速对表原值： C
详细解析标注： C
有向图邻接矩阵的第 V 行中 1 的个数是顶点 V 的出度，而有向图中顶点的度为入度与出度之和，I 错。无向图的邻接矩阵一定是对称矩阵，但当有向图中任意两个顶点之间有边相连，且是两条方向相反的有向边时，有向图的邻接矩阵也是一个对称矩阵，Ⅱ 错。最小生成树中的 n-1条边不能保证是图中权值最小的 n-1 条边，因为权值最小的 n-1 条边并不一定能使图连通。在下图中，左图的最小生成树如下图所示，权值为 3 的边不在其最小生成树中。有向无环图的拓扑序列唯一并不能唯一确定该图。在下图所示的两个有向无环图中，拓扑序列都为V1, V2, V3, V4，IV 错。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q51¶
速对表原值： A
详细解析标注： A
比如 1→3→2，邻接矩阵不是上三角也不是下三角矩阵，但是存在拓扑序列{1，3，2}，A 错误。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q52¶
速对表原值： D
详细解析标注： D
给出有向图 G=（V，E），对于 V 中顶点的线性序列（Vi1，Vi2....，Vin），如果满足如下条件：若在 G 中顶点 Vi 到 Vj 有一条路径，则在序列中顶点 Vi 必在顶点 Vj 之前，则该序列称为 G 的一个拓扑序列。根据定义可知，顶点 Vi 顶点 Vj 之前，并不能说明顶点 Vi 和顶点 Vj 之间邻接关系，但不可能存在一条从 Vj 到 Vi 的路径，因为存在从 Vj 到 Vi 的路径则说明顶点 Vj 必须在顶点 Vi 之前，这与题目产生矛盾。因此答案应选择 D。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q53¶
速对表原值： D
详细解析标注： D
该图中存在回路，该回路构成一个顶点个数大于 1 的强连通分量。
Q54¶
速对表原值： D
详细解析标注： D
I 正确，DFS 在进行遍历的时候，按照退出递归的顺序输出顶点序号可以得到逆拓扑排序，再逆置就可以得到拓扑排序。II 正确，Dijkstra 是用来求最短路径的，更新的策略和 Prim 不同，不能生成最小生成树。III、IV 正确。IV 中的拓扑序列不唯一，但是一定有且只有一条有序的拓扑序列。相反，能得到有序的拓扑序列的有向图一定是上三角或者下三角矩阵这句话也是对的。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q55¶
速对表原值： C
详细解析标注： C
对于 A，解决拓扑排序问题用到的是 AOV 网（顶点表示活动的网），而解决关键路径问题用到的是 AOE 网（边表示活动的网）。对于 B，从源点到汇点的最长路径称作关键路径。对于 C，在 AOE 网中，如果有环，则可以认为环上的活动都以自身的结束作为自身可能开始的条件，那么将不存在所有活动都完成的状态，也就不存在关键路径。对于 D，因为关键路径可能是不唯一的，所以某个活动的时间缩短，可能并不能使另一条关键路径的长度也缩短。
Q56¶
速对表原值： B
详细解析标注： B
一个关键活动提前完成，只能让这条关键路径变成非关键路径。当关键路径不止一条的时候，单单提高一条关键路径上关键活动的速度，是不能缩短整个工程工期的。所以，并不是网中任何一个关键活动提前完成，整个工程都能提前完成。但如果网中任何一个关键活动延期完成，整个工程一定延期。
Q57¶
速对表原值： D
详细解析标注： D
可以知道，缩短单条关键路径的长度不能缩短整个工程的关键路径长度，必须同时减小所有关键路径长度才会产生新的关键路径，也就是关键路径长度才会减小。该 AOE 网有三条关键路径，分别是：
①〔公式/符号见原页版面片段〕1 → 〔公式/符号见原页版面片段〕2 → 〔公式/符号见原页版面片段〕5 → 〔公式/符号见原页版面片段〕7，对应关键路径上的活动是〔公式/符号见原页版面片段〕1〔公式/符号见原页版面片段〕4〔公式/符号见原页版面片段〕7
②〔公式/符号见原页版面片段〕1 → 〔公式/符号见原页版面片段〕3 → 〔公式/符号见原页版面片段〕5 → 〔公式/符号见原页版面片段〕7，对应关键路径上的活动是〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕5〔公式/符号见原页版面片段〕7
③〔公式/符号见原页版面片段〕1 → 〔公式/符号见原页版面片段〕4 → 〔公式/符号见原页版面片段〕6 → 〔公式/符号见原页版面片段〕7，对应关键路径上的活动是〔公式/符号见原页版面片段〕3〔公式/符号见原页版面片段〕6〔公式/符号见原页版面片段〕8，可以知道只有一条关键路径
①
②公共的关键活动〔公式/符号见原页版面片段〕7，要想缩短两个活动能同时缩短三条关键路径，那么必须包含〔公式/符号见原页版面片段〕7，另外一个从〔公式/符号见原页版面片段〕3〔公式/符号见原页版面片段〕6〔公式/符号见原页版面片段〕8中选一个，答案选 D。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q58¶
速对表原值： A
详细解析标注： A
此题可用关键路径常规的求解方法，一步步计算。〔公式/符号见原页版面片段〕 源点 = 0，〔公式/符号见原页版面片段〕 =〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕 ，从前往后计算最早开始事件的值，将其余从源点到〔公式/符号见原页版面片段〕的所有路径中，路径长度比ve 小的且终点为〔公式/符号见原页版面片段〕的边从图中删除和 ve 值相等的路径上的边不用删除），即删除的一定是非关键的边。当〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕)求解完毕时，剩余能连通源点和汇点的路径都是关键路径。可得到如下图所示的结果，由此可知，AOE 图的关键路径长度是 16。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q59¶
速对表原值： A
详细解析标注： A
bdcg, bdeh, bfh 都是关键路径，关键路径长是 27，只有活动 a 不是关键路径上的活动。同学们可手动计算一下 a 的时间余量，最晚开始时间是 9，最早开始时间是 0，所以时间余量是9。
Q60¶
速对表原值： A
详细解析标注： A
增加活动〔公式/符号见原页版面片段〕3或者增加活动〔公式/符号见原页版面片段〕7的任意时间，工程的工期一定延长，说明〔公式/符号见原页版面片段〕3和〔公式/符号见原页版面片段〕7一定是关键路径上的活动，通过〔公式/符号见原页版面片段〕3的路径只有一条，即〔公式/符号见原页版面片段〕1 → 〔公式/符号见原页版面片段〕4 → 〔公式/符号见原页版面片段〕6 → 〔公式/符号见原页版面片段〕7，对应关键路径上的活动是〔公式/符号见原页版面片段〕3〔公式/符号见原页版面片段〕6〔公式/符号见原页版面片段〕8，关键路径长度=6+2+1=9。而通过〔公式/符号见原页版面片段〕7的路径有两条一条是〔公式/符号见原页版面片段〕1 → 〔公式/符号见原页版面片段〕3 → 〔公式/符号见原页版面片段〕5 → 〔公式/符号见原页版面片段〕7，〔公式/符号见原页版面片段〕1 → 〔公式/符号见原页版面片段〕2 → 〔公式/符号见原页版面片段〕5 →〔公式/符号见原页版面片段〕7，但前者路径长度为 1+4+3=8 不是关键路径。所以后者必然为关键路径，而后者对应关键路径上的活动是〔公式/符号见原页版面片段〕1〔公式/符号见原页版面片段〕4〔公式/符号见原页版面片段〕7，所以〔公式/符号见原页版面片段〕1+3+3=9，〔公式/符号见原页版面片段〕1=3，答案选 A。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q61¶
速对表原值： C
详细解析标注： C
BFS 适合求无权图或者等权图的最短路径，其核心思想是看结点在 BFS 遍历的第几层最短路径长度就是多少。第一层有结点 1,6，第二层有结点 3,5,7。所以路径长度为 2 的有 3,5,7 共 3个顶点。
Q62¶
速对表原值： D
详细解析标注： D
第一轮前，dist 数组为{8,8,8}，三个顶点都可以选取：
①当第一轮选取 V1，dist变为{8,8,5}；
②当第一轮选取V2，dist变为{8,8,8}；
③当第一轮选取V4，dist变为{5,8,8}；所以只有D是正确的。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q63¶
速对表原值： C
详细解析标注： C
Dijkstr 算法中，dist 数组的更新原理是：每次选出当前未确定顶点中 dist 最小的顶点作为新的确定顶点，并用它到各邻接点的距离尝试“松弛”更新这些邻接点的 dist 值。Dijkstra算法的 dist 更新公式为：〔公式/符号见原页版面片段〕[〔公式/符号见原页版面片段〕] = min(〔公式/符号见原页版面片段〕[〔公式/符号见原页版面片段〕], 〔公式/符号见原页版面片段〕[〔公式/符号见原页版面片段〕] + 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕,〔公式/符号见原页版面片段〕))其中：k：本轮选出的当前 dist 最小的未确定顶点；j：k 的邻接顶点；w(k, j)：边
原页版面片段（用于核对图表、公式、矩阵或代码）
Q64¶
速对表原值： A
详细解析标注： A
首先题目是反邻接表，即边表都是入边，有向图如下左图所示。逆拓扑排序是从出度为 0 的顶点开始，每轮输出一个出度为 0 的顶点，然后消除与之相关的入边，反复操作直到所有顶点全部输出。（若不能输出所有顶点即表示该有向图存在环）逆拓扑排序过程如下右图所示。
Q65¶
速对表原值： D
详细解析标注： D
A 错误，关键路径有两条：(v0,v1,v4,v6,v8)或(v0,v1,v4,v7,v8)，长度均为 18，即关键路径长度位 18。
B 错误，活动a6的最早开始时间和最晚开始时间是 5、8，若在 t=9 才开始，工程一定会延期。
C 错误，活动a5的最早开始时间和最晚开始时间是 4、6，时间余量是 6-4=2。
D 正确，事件v4的最晚发生时间是关键路径上的事件，最晚发生时间是 关键路径长度-11=18-11=7。
原页版面片段（用于核对图表、公式、矩阵或代码）
