c++数据结构将一个无向图的邻接矩阵转换为邻接表

在C++中，将一个无向图的邻接矩阵表示转换成邻接表（Adjacency List）可以提高空间效率，特别是当图中存在大量稀疏连接（即边的数量远小于节点总数的平方）时。邻接列表通过为每个节点存储一个链接到其邻居的链表，而不是一个二维数组。

以下是基本步骤：

1. **创建邻接表**：对于无向图的每一个节点，创建一个单独的链表或者使用哈希表（如std::unordered_map），键是节点，值是一个vector或list，用于存储与该节点相连的所有其他节点。

struct Node {
    int value;
    std::list<int> neighbors; // 使用list是因为插入删除操作更高效
};

// 如果使用哈希表
using Graph = std::unordered_map<int, std::vector<int>>;

2. **遍历矩阵**：遍历原邻接矩阵，对于每个节点i，检查其对应的矩阵元素j。如果非零，则将节点j添加到节点i的邻接表中，并反之（因为图是无向的）。

for (int i = 0; i < num_nodes; ++i) {
    for (int j = 0; j < num_nodes; ++j) {
        if (adj_matrix[i][j] != 0) {
            adj_list[i].push_back(j);
            // 如果图是无向的，也把j添加到i的邻居列表里
            adj_list[j].push_back(i);
        }
    }
}

3. **清理矩阵**：完成上述操作后，邻接矩阵通常不再需要保留，因为它已经转化为邻接表形式。