在求 AOE网的关键路径时，若该有向图用邻接矩阵表示且第i 列值全为∞，则（ ）。

A. 若关键路径存在，第i 个顶点一定是起点 B. 若关键路径存在，第i 个顶点一定是终点 C. 关键路径不存在 D. 该有向图对应的无向图存在多个连通分量

正确答案：A

结论

选 A。在矩阵约定 a[u][v] 表示 u→v 时，第 i 列全为 ∞ 表示没有入边，即顶点 i 入度为零；在 AOE 网存在关键路径且源点唯一的前提下，它就是起点。

推导

邻接矩阵的列统计入边、行统计出边。入度为零的顶点只能作为工程源点候选；“关键路径存在”以及 AOE 网通常要求唯一源点，才可判定为起点。详见 邻接矩阵列与入度。

易错点

列全 ∞ 只说明无入边，不说明终点（终点应看出度为零，即行全 ∞），也不能单独推出图不连通；必须结合 AOE 网的单一源点和关键路径存在前提。