无向图邻接矩阵压缩一维数组

### 将无向图的邻接矩阵压缩存储到一维数组的方法

对于无向图而言，其邻接矩阵是对称的。这意味着如果节点 i 和 j 之间有一条边，则 G[i][j]=G[j][i] 。因此可以只保存上三角或下三角部分的数据来减少空间占用。

#### 计算方法
假设有一个大小为 n×n 的邻接矩阵 M ，那么可以通过下面的方式将其映射至长度为 n(n−1)/2 的一维数组 A 中：

- 对于任意一对 (i,j)，其中 0≤i<j<n ,则对应的索引位置 k 可以通过公式计算得出：k=i∗(n−1)−i∗(i+1)/2+j−i−1 或者更简单的形式是 k=n*i+i*(i-1)//2+j-i

这种映射方式能够有效地节省一半以上的内存空间，并且保持原有的连通性信息不变[^1]。

#### Python 实现示例
下面是具体的Python实现代码，用于展示如何将一个给定的无向图邻接矩阵转换成紧凑的一维数组表示法:

def compress_adj_matrix(matrix):
    n = len(matrix)
    compressed_array = []
    
    for i in range(n):
        for j in range(i + 1, n):  
            if matrix[i][j]:
                index = int((n * i + j - ((i + 1) * i / 2)) - i - 1)
                while len(compressed_array)<=index:
                    compressed_array.append(float('inf'))
                compressed_array[index] = matrix[i][j]

    return compressed_array


# 测试案例
adjacency_matrix = [
    [0, 1, 0, 1],
    [1, 0, 1, 1],
    [0, 1, 0, 0],
    [1, 1, 0, 0]
]

print("原始邻接矩阵:")
for row in adjacency_matrix:
    print(row)

compressed_representation = compress_adj_matrix(adjacency_matrix)
print("\n压缩后的一维数组:", compressed_representation)

上述程序会输出原邻接矩阵以及经过压缩处理后的结果。需要注意的是，在实际应用中可能还需要记录哪些位置对应着有效的边权重值，以便后续解压还原时使用。