如何对无环有向图中的顶点重新编号，使得该图的邻接矩阵中所有的 1 都集中到对角线以上？

[tag_link]

参考答案

对该 DAG 进行拓扑排序，并按拓扑序列依次编号为 1,2,…,n。对任意弧 i→j，拓扑序都要求 i 排在 j 之前，因此新编号满足 i<j；对应的邻接矩阵元素 A[i][j] 只可能位于主对角线上方。拓扑排序可用入度为 0 的顶点逐步删除，若有多个候选顶点，任取其一即可。

推导

DAG 必然存在拓扑序。重新编号后，若矩阵下三角位置 A[i][j]（i>j）为 1，就表示存在弧 i→j，与拓扑序中 i 应排在 j 前矛盾。因此所有 1 均在主对角线上方；该性质不要求拓扑序唯一。

易错点

只按原编号排序不一定成立；必须使用拓扑序。矩阵上三角方向取决于约定的弧方向和编号顺序，本文约定 A[i][j]=1 表示 i→j。