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

无向图邻接矩阵对角线

无向图的邻接矩阵是对图中各个顶点之间边的连接情况进行编码的一种方式，它是一个二维数组，其中行和列对应图中的顶点，矩阵的元素a[i][j]表示顶点i和顶点j之间是否存在一条边。对于无向图，由于边是双向的，所以邻接矩阵是对称的，即a[i][j] = a[j][i]。

无向图邻接矩阵的对角线指的是从左上角到右下角的那条线，即包含所有主对角线元素的部分，这些元素a[i][i]通常代表每个顶点自身是否连接有自环。在大多数情况下，无向图的邻接矩阵对角线上的元素值为0，因为无向图不包含自环（除非特别设计为有自环）。