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

素颜马尾好姑娘i 2023-10-16 17:27 82阅读 0赞

#### 文章目录 ####

*  一、COO
 *  二、CSR
 *  三、adj\_coo
 *  四、adj\_csr
 *  五、格式转换代码

> **稀疏图**：数据结构中对于稀疏图的定义为：有很少条边或弧（边的条数  ∣ E ∣ |E| ∣E∣ 远小于  ∣ V ∣ 2 |V|^2 ∣V∣2）的图称为**稀疏图**，反之边的条数  ∣ E ∣ |E| ∣E∣ 接近  ∣ V ∣ 2 |V|^2 ∣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][1]

**图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][2]

**图2 CSR表示**

## 三、adj\_coo ##

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

**图3 adj\_coo表示**

## 四、adj\_csr ##

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

**图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)

运行结果如下图所示：  
![图五][da722c01d3cb4014bd561186d1e75704.png]

[1]: https://img-blog.csdnimg.cn/da3d4f67d94b41f8a311738751fad63c.png#pic_center
[2]: https://img-blog.csdnimg.cn/a3c48335ba3248c5ad02d64d9c298ea6.png#pic_center
[3]: https://img-blog.csdnimg.cn/74c6fdad473b49cc95ff1b7c8664669c.png#pic_center
[4]: https://img-blog.csdnimg.cn/dcbdc2e75ac24ad787286cc50829d549.png#pic_center
[da722c01d3cb4014bd561186d1e75704.png]: https://img-blog.csdnimg.cn/da722c01d3cb4014bd561186d1e75704.png