COO、CSR、adj_coo、adj_csr详解：稀疏矩阵与稀疏邻接矩阵的存储格式及转换

稀疏图：数据结构中对于稀疏图的定义为：有很少条边或弧（边的条数 $|E|$ 远小于 $|V{|}^2$）的图称为稀疏图，反之边的条数 $|E|$ 接近 $|V{|}^2$，称为稠密图。采用直观的办法来存储图往往会造成极大的空间浪费，因此需要采取其他方式压缩存储空间。

一、COO

1. 对于稠密图，我们往往以矩阵的方式存储结点的连接关系。如图1a所示，对于矩阵 matrix，matrix[i][j] = x 表示结点 i 与结点 j 之间的边的长度为 x。我们可以看到在图1a的矩阵 matrix 中，除了少数结点间有边相连，大多数的存储空间都浪费了。
2. 对于稀疏图，最直观的压缩存储方式是只存储矩阵 matrix 中的非零元素以及这些元素的位置，也就是以三元组的方式存储 (i, j, x)。(i, j, x) 同样表示结点 i 与结点 j 之间的边的长度为 x，如图1b所示。
3. 使所有三元组的横坐标单独组成 row 数组，纵坐标单独组成 column 数组，数值单独组成 data 数组就形成了稀疏矩阵的 COO表示，如图1c所示。

图1 COO表示

二、CSR

1. 对于结点数量比较多，并且远大于边数量的稀疏矩阵，上一小节中介绍的COO表示已经能够节省很多存储空间了，那我们还能不能进一步节省更多的空间呢？
2. 当然可以！我们观察上一小节中得到的 COO表示（如图2b所示），row 数组中各三元组的横坐标 按序排列，因此 相同的横坐标会连在一起，这何尝不是一种 数据重复？
3. 我们保持 column 数组和 data 数组 不变。将 row 数组改为 row offsets：不再记录每一个元素的横坐标，只记录每一行的第一个元素在 data 数组中的下标，最后再额外记录总的元素个数。如图2c所示。
   • 新的数组 row offsets 就像书签一样，其中的第 i 个元素 ro[i]就代表了 data[ro[i]] 与 data[ro[i+1]] 之间的元素的横坐标为 i（包括data[ro[i]] 但不包括 data[ro[i+1]]）。
   • 如图2中，我们分别用蓝、黄、绿、橙代表不同的四行的元素。
     第 0 行的第一个元素为6，data 数组中其下标为 0，故 ro[0]=0。
     第 1 行的第一个元素为3，data 数组中其下标为 2，故 ro[1]=2。
     第 2 行的第一个元素为5，data 数组中其下标为 4，故 ro[2]=4。
     第 3 行的第一个元素为7，data 数组中其下标为 5，故 ro[3]=5。
     data 数组中共有 7 个元素，故 ro[4]=7。

图2 CSR表示

三、adj_coo

第一小节中我们讨论了普通稀疏图的矩阵转化为COO表示。但如果邻接矩阵中只记录了两个结点是否相连，并没有记录边的信息（如图3a），我们便不需要记录 data 数据，如此可以进一步压缩存储空间。

图3 adj_coo表示

四、adj_csr

与adj_coo情况类似，如果邻接矩阵中只记录了两个结点是否相连，并没有记录边的信息（如图4a），我们便不需要记录 data 数据，如此可以进一步压缩存储空间。

图4 adj_csr表示

五、格式转换代码

这里仅展示 adj_coo 转 adj_csr 的代码：

def adjcoo2adjcsr(adj_coo, node_count):
    sour = adj_coo[0]
    dist = adj_coo[1]
    adjs = []
    last = -1
    for i in range(node_count):
        try:
            index = sour.index(i)
        except:
            index = last + 1
        else:
            last = index
        finally:
            adjs.append(index)
    adjs.append(len(dist))
    print(adjs)
    print(dist)


adj_coo = [[0, 0, 1, 1, 2, 3, 3],
           [0, 1, 1, 2, 0, 2, 3]]
adjcoo2adjcsr(adj_coo, 4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行结果如下图所示：