若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。

拓扑排序

A. 存在，且唯一

B. 存在，且不唯一

C. 存在，可能不唯一

D. 无法确定是否存在

[tag_link]

正确答案：C

主对角线以下元素均为零，表示只可能存在 i→j (i<j) 的边，不可能沿边从较大编号回到较小编号，所以图中无有向环，一定存在拓扑序列。

但拓扑序列未必唯一。例如 3 个顶点只有边 1→3、2→3 时，邻接矩阵是严格上三角矩阵，1,2,3 与 2,1,3 都是合法拓扑序。因此选 C。

反过来，DAG 在任意编号下的邻接矩阵未必是三角矩阵；按某个拓扑序给顶点重新编号后，才可得到严格上三角矩阵。