修改无向图的邻接矩阵类定义,添加方法实现根据邻接矩阵结构获取邻接表结构。
时间: 2023-10-18 16:07:31 浏览: 110
好的,我可以为你解答这个问题。
首先,我们需要了解无向图的邻接矩阵和邻接表的概念。无向图的邻接矩阵是一个二维矩阵,其中第 i 行第 j 列的元素表示第 i 个节点和第 j 个节点是否相邻,如果相邻则为 1,否则为 0。而无向图的邻接表则是由一组链表组成,每个链表代表一个节点,链表中存储了与该节点相邻的节点列表。
那么如何将邻接矩阵转换为邻接表呢?我们可以遍历整个邻接矩阵,对于每个节点,将与其相邻的节点加入到对应的链表中。具体实现可以参考下面的代码:
```c++
#include <vector>
class Graph {
private:
int n; // 节点数
std::vector<std::vector<int>> matrix; // 邻接矩阵
std::vector<std::vector<int>> list; // 邻接表
public:
Graph(int n) {
this->n = n;
this->matrix = std::vector<std::vector<int>>(n, std::vector<int>(n));
this->list = std::vector<std::vector<int>>(n);
}
void addEdge(int u, int v) {
matrix[u][v] = 1;
matrix[v][u] = 1; // 无向图需要将对称位置也设为 1
}
void matrixToList() {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) { // 只需要遍历对称位置的一半
if (matrix[i][j] == 1) {
list[i].push_back(j);
list[j].push_back(i); // 对称位置也需要加入
}
}
}
}
};
```
在上面的代码中,我们定义了一个 Graph 类,其中包含了邻接矩阵和邻接表两种表示方式,以及相应的转换方法。addEdge 方法用于向邻接矩阵中添加边,而 matrixToList 方法则是将邻接矩阵转换为邻接表的关键方法。在 matrixToList 方法中,我们遍历了邻接矩阵的对称位置,如果发现两个节点相邻,则将它们加入到对应的链表中。
通过调用 matrixToList 方法,我们就可以将邻接矩阵转换为邻接表了。需要注意的是,由于邻接表的空间复杂度比邻接矩阵要高,因此在实际应用中需要根据具体情况选择使用哪种表示方式。
阅读全文