如何用一维数组压缩存储带权有向无环图的邻接矩阵

我们可以使用一维数组来压缩存储带权有向无环图的邻接矩阵，具体做法是将矩阵中的每个元素按行优先顺序存储在一维数组中，并且只存储下三角部分或上三角部分（因为矩阵是对称的）。对于权值为0的边可以不存储，以节省空间。由于图是有向无环的，所以对角线上的元素都为0，也可以不存储。

举个例子，假设有以下3个结点的带权有向无环图：

0--2--1
|\/ |
|/\ |
3---4

邻接矩阵为：

0 2 0 1 0
0 0 0 3 4
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

如果我们只存储下三角部分（包括对角线），则一维数组为：

[0,2,0,1,0,0,3,4,0,0]

如果我们只存储上三角部分（不包括对角线），则一维数组为：

[2,1,3,4]