用邻接矩阵存储无向图时,邻接矩阵为什么是对称矩阵?
时间: 2023-10-23 15:44:33 浏览: 63
当使用邻接矩阵来表示无向图时,对于无向图中的每条边 (i,j),我们需要在邻接矩阵中将相应的位置 a[i][j] 和 a[j][i] 标记为 1,表示这两个顶点之间存在连边。
由于无向图中的边是没有方向的,即从顶点 i 到 j 的边与从顶点 j 到 i 的边是等价的,因此邻接矩阵是对称的。也就是说,对于任意的 i 和 j,邻接矩阵中的 a[i][j] 和 a[j][i] 应该相等,因此邻接矩阵是对称矩阵。
如果邻接矩阵不是对称矩阵,说明在无向图中存在一些边只被记录了一次,这样就无法正确地表示无向图中的边信息。因此,邻接矩阵必须是对称矩阵。
相关问题
使用邻接矩阵存储无向图
使用邻接矩阵存储无向图的步骤如下:
1. 定义一个顶点类型的一维数组,用于存储顶点。
2. 定义一个int类型的二维数组,用于存储边。对于无向图,邻接矩阵是一个对称矩阵,即edge[i][j] = edge[j][i]。
3. 定义两个int型变量,分别存储顶点数、边数。
4. 初始化邻接矩阵,将所有元素初始化为0。
5. 根据图的实际情况,将边的信息存储到邻接矩阵中。对于无向图,如果顶点i和顶点j之间有一条边,则将edge[i][j]和edge[j][i]的值都设为1。
6. 根据需要,可以输出邻接矩阵或者进行其他操作。
下面是一个使用邻接矩阵存储无向图的示例代码:
```c++
#include <iostream>
using namespace std;
const int max_vertex_num = 100;
typedef char VexType; // 顶点类型
typedef int EdgeType; // 边权值类型
class AMGraph {
public:
VexType vex[max_vertex_num]; // 存储顶点
EdgeType edge[max_vertex_num][max_vertex_num]; // 存储边
int vex_num, edge_num; // 顶点数、边数
// 初始化邻接矩阵
void Init() {
for (int i = 0; i < vex_num; i++) {
for (int j = 0; j < vex_num; j++) {
edge[i][j] = 0;
}
}
}
// 添加边
void AddEdge(int i, int j) {
edge[i][j] = 1;
edge[j][i] = 1;
}
// 输出邻接矩阵
void Print() {
for (int i = 0; i < vex_num; i++) {
for (int j = 0; j < vex_num; j++) {
cout << edge[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
AMGraph g;
g.vex_num = 5;
g.edge_num = 6;
g.vex[0] = 'A';
g.vex[1] = 'B';
g.vex[2] = 'C';
g.vex[3] = 'D';
g.vex[4] = 'E';
g.Init();
g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(1, 2);
g.AddEdge(1, 3);
g.AddEdge(2, 3);
g.AddEdge(3, 4);
g.Print();
return 0;
}
```
说明邻接矩阵存储无向图和邻接表存储无向图以及分析二者的优缺点
邻接矩阵和邻接表都是存储无向图的数据结构。
邻接矩阵是一个二维数组,其中 $matrix[i][j]$ 表示节点 $i$ 和节点 $j$ 是否相连。对于无向图来说,邻接矩阵是一个对称的矩阵。
邻接表则是使用链表来表示每个节点的邻居节点。每个节点有一个链表,链表中存储了该节点的所有邻居节点。
邻接矩阵和邻接表在存储无向图时,各有其优缺点:
邻接矩阵的优点:
- 查找两个节点之间是否有边的时间复杂度为 $O(1)$。
- 方便计算度数和邻居节点。
- 对于稠密图(边数接近于节点数的平方),邻接矩阵更加节省空间。
邻接矩阵的缺点:
- 对于稀疏图(边数远小于节点数的平方),邻接矩阵会浪费大量的空间。
- 添加或删除节点或边的时间复杂度为 $O(n^2)$。
邻接表的优点:
- 对于稀疏图,邻接表可以节约空间。
- 添加或删除节点或边的时间复杂度为 $O(1)$。
邻接表的缺点:
- 查找两个节点之间是否有边的时间复杂度为 $O(k)$,其中 $k$ 是节点的度数。
- 计算度数和邻居节点可能需要遍历整个链表,时间复杂度为 $O(n)$。