用邻接矩阵存储无向图时，邻接矩阵为什么是对称矩阵？

当使用邻接矩阵来表示无向图时，对于无向图中的每条边 (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. 根据需要，可以输出邻接矩阵或者进行其他操作。

下面是一个使用邻接矩阵存储无向图的示例代码：

#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;
}

用邻接矩阵存储无向图和用邻接表存储无向图对二者的说明以及分析二者的优缺点

邻接矩阵是一种二维数组，其中的元素表示两个顶点之间是否有边连接。对于无向图，邻接矩阵是对称的，即 $A_{ij}=A_{ji}$。当 $A_{ij}=1$ 时，表示顶点 $i$ 和 $j$ 之间有边连接，否则表示它们之间没有边连接。邻接矩阵可以通过下标快速访问两个顶点之间是否有边连接，时间复杂度为 $O(1)$，但是它需要 $O(n^2)$ 的空间复杂度，其中 $n$ 表示顶点数。

邻接表是一种链表的数组，其中每个链表表示一个顶点的邻居节点。对于无向图，每个无向边都会在两个顶点的邻接表中各出现一次。邻接表可以动态的添加和删除边，而且它的空间复杂度取决于边的数量，即 $O(m)$，其中 $m$ 表示边数。但是，访问两个顶点之间是否有边连接的时间复杂度为 $O(k)$，其中 $k$ 表示一个顶点的平均邻居数量。

对于稠密图（即边数与顶点数的比值接近于 1），邻接矩阵比邻接表更适用，因为它的访问时间复杂度为 $O(1)$，并且它的空间复杂度为 $O(n^2)$，与边数无关。而对于稀疏图（即边数与顶点数的比值远小于 1），邻接表比邻接矩阵更适用，因为它的空间复杂度为 $O(m)$，与顶点数无关，而且它的访问时间复杂度为 $O(k)$，与边数成正比，比邻接矩阵更高效。