请说明，只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0

对于任何一个有向无环图，都存在拓扑排序，即将图中的顶点排成一个序列，使得所有的有向边从排在前面的顶点指向排在后面的顶点。这个序列就是一个拓扑序。对于任何一条有向边 (i, j)，在拓扑序中，顶点 i 出现在顶点 j 的前面。因此，如果我们将拓扑序中排在前面的顶点放在矩阵的前面，排在后面的顶点放在矩阵的后面，那么矩阵中主对角线以下的元素全部为0。这是因为，在拓扑序中排在前面的顶点不可能指向排在后面的顶点，因此在矩阵中主对角线以下的元素就是0。因此，只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。

相关问题

用张铭编写的《数据结构与算法》证明： 只要适当地排列顶点的次序， 就能使有向无环图的邻接矩阵中主对角线以下的元 素全部为 0

假设有向无环图的顶点集为 {v1, v2, ..., vn}，我们可以通过对顶点集进行拓扑排序来得到一个顶点序列 {vi1, vi2, ..., vin}，使得对于任意的 i < j，不存在从 vij 指向 vii 的边。这样的顶点序列可以通过 Kahn 算法或 DFS 实现。

接下来，我们根据拓扑序列来构造邻接矩阵。设 A 为邻接矩阵，其中 A[i][j] 表示从 vi 到 vj 是否存在一条边。由于拓扑排序的性质，对于任意的 i < j，vj 不可能指向 vi，因此 A[j][i] 必然为 0。

由于有向无环图中不存在环，因此不存在从一个顶点出发经过若干个顶点后回到该顶点的情况。因此，对于任意的 i，vj 不可能指向 vi，也就是说 A[i][i+1] 至 A[i][n-1] 都必须为 0。因此，邻接矩阵 A 中主对角线以下的元素全部为 0。

综上所述，只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为 0。