题目

已知有 6 个顶点（顶点编号为 0~5）的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。

[4, 6, ∞, ∞, ∞,  5, ∞, ∞, ∞,  4, 3, ∞,  ∞, 3,  3]

上述 15 个元素依次对应严格上三角部分：第 0 行（5 个）→ 第 1 行（4 个）→ 第 2 行（3 个）→ 第 3 行（2 个）→ 第 4 行（1 个）。

要求：

(1) 写出图 G 的邻接矩阵 A。

(2) 画出有向带权图 G。

(3) 求图 G 的关键路径，并计算该关键路径的长度。

解析

预备：还原上三角矩阵的存储

题面给的一维数组 [4, 6, ∞, ∞, ∞, 5, ∞, ∞, ∞, 4, 3, ∞, ∞, 3, 3] 共 15 个元素，对应严格上三角部分（共 项）。按行展开：

• 第 0 行（5 项）：A[0][1]=4, A[0][2]=6, A[0][3]=∞, A[0][4]=∞, A[0][5]=∞
• 第 1 行（4 项）：A[1][2]=5, A[1][3]=∞, A[1][4]=∞, A[1][5]=∞
• 第 2 行（3 项）：A[2][3]=4, A[2][4]=3, A[2][5]=∞
• 第 3 行（2 项）：A[3][4]=∞, A[3][5]=3
• 第 4 行（1 项）：A[4][5]=3

下三角与对角线全部为 ∞（不画自环、有向图）。

(1) 邻接矩阵 A

(2) 有向带权图 G

按矩阵中的有限值取出 7 条弧：

弧	权
0 → 1	4
0 → 2	6
1 → 2	5
2 → 3	4
2 → 4	3
3 → 5	3
4 → 5	3

(3) 关键路径与长度

答案：关键路径 0 → 1 → 2 → 3 → 5，长度 16。

步骤 1：算每个顶点的最早发生时间 （按拓扑序 0, 1, 2, 3, 4, 5 正向取入边贡献最大值）：

顶点	推导
0	起点	0
1		4
2		9
3		13
4		12
5		16

最短工期 = ve(5) = 16。

步骤 2：算每个顶点的最迟发生时间 （按逆拓扑序，从 vl(5)=ve(5) 起步）：

顶点	推导
5	汇点	16
4		13
3		13
2		9
1		4
0		0

步骤 3：算各活动的余量，找出关键活动（余量 = ，0 即关键）：

活动	弧 i→j	w	ee	le	余量	关键
a₁	0→1	4	0	0	0	★
a₂	0→2	6	0	3	3
a₃	1→2	5	4	4	0	★
a₄	2→3	4	9	9	0	★
a₅	2→4	3	9	10	1
a₆	3→5	3	13	13	0	★
a₇	4→5	3	12	13	1

关键活动：a₁, a₃, a₄, a₆。串成关键路径：

与 一致。

编者注（生僻术语）：上三角压缩存储是节省空间的常用手法——n×n 方阵只需 项即可（自环不存）。本题考点其实是两步：(1)(2) 考"压缩存储 ↔ 矩阵 ↔ 图"的相互转换，(3) 考关键路径计算。把第一步图建准是后续不出错的关键。