有向图和无向图的邻接矩阵表示法及其特点

有向图和无向图都是图论中的两种基本结构，它们描述了顶点之间的连接关系。邻接矩阵是常用的图数据结构之一，用于表示图中各个顶点之间的边。

**1. 有向图邻接矩阵表示法：**
有向图的邻接矩阵是一个二维数组，其中行代表起点，列代表终点，矩阵中的每个元素a[i][j]（0-based索引）表示从第i个顶点到第j个顶点是否存在一条有向边。如果是有向边，则该元素为1或非零；若不存在边，则为0。由于是单向的，邻接矩阵通常是对称性的破坏，即a[i][j]不等于a[j][i]。

**特点：**
- **空间效率高**: 当图中的边数接近于顶点数量的平方时，存储密度较高。
- **查询速度快**: 可直接通过矩阵元素查找两个顶点间是否有边，时间复杂度为O(1)。
- **插入和删除操作较慢**: 如果要添加或删除一条边，需要修改对应的矩阵元素，时间复杂度为O(n)，n为顶点数量。

**2. 无向图邻接矩阵表示法：**
对于无向图，邻接矩阵是对称的，即a[i][j] = a[j][i]，表示两个顶点之间是否有边。同样，元素值为1或其他非零值表示存在边，0表示没有边。

**特点：**
- **空间需求大**: 对于完全连通的无向图，邻接矩阵会占用双倍的空间，因为需要保存双向关系。
- **查询速度相同**: 查询、插入和删除操作的时间复杂度仍然为O(1)。

**相关问题--:**
1. 除了邻接矩阵，还有哪些方法可以表示有向图和无向图？
2. 在稀疏图中，邻接矩阵是否是最优的数据结构？为什么？
3. 如何通过邻接矩阵快速判断两个顶点是否互为邻居？

相关问题

7-3邻接矩阵 邻接矩阵表示法创建无向图 分数 10

邻接矩阵是一种表示图的数据结构，其中图中的每个节点对应于矩阵中的一个元素，矩阵中的值表示两个节点之间是否有边相连。对于无向图而言，如果节点i和节点j之间存在一条边，则邻接矩阵中第i行第j列和第j行第i列的值都为1；如果两个节点之间没有边相连，则对应位置的值为0。

创建无向图的邻接矩阵表示法需要以下步骤：
1. 创建一个N * N的二维矩阵，其中N为图中节点的数量；
2. 将矩阵中的所有元素初始化为0；
3. 对于每一条边(i, j)，将邻接矩阵中第i行第j列和第j行第i列的值都设置为1。

举个例子，假设有如下无向图：

    1 -- 2
   / \   |
  /   \  |
 4-----3-5

它的邻接矩阵表示法为：

  0 1 2 3 4 5
0 0 1 0 0 1 0
1 1 0 1 0 0 1
2 0 1 0 1 0 1
3 0 0 1 0 1 1
4 1 0 0 1 0 0
5 0 1 1 1 0 0

邻接矩阵表示法创建无向图

邻接矩阵是一种表示图的方式，用矩阵表示图中各个顶点之间的关系。对于无向图，邻接矩阵是一个对称矩阵，矩阵中的每个元素表示相邻顶点之间的边的数量或权重。

创建无向图的邻接矩阵表示法的步骤如下：

1. 创建一个 n × n 的矩阵，其中 n 是图中顶点的数量。

2. 在矩阵中标记顶点的编号，可以按照任意顺序给顶点编号。

3. 对于每条边 (i, j)，将矩阵中第 i 行第 j 列和第 j 行第 i 列的元素都置为 1，表示这两个顶点之间有一条边。

4. 如果图中有权重，则将矩阵中的元素改为相应的权重值。

下面是一个示例，展示如何用邻接矩阵表示法创建一个无向图：

假设有一个无向图，包含 5 个顶点和 7 条边，如下所示：

   1---2
   |\ /|
   | X |
   |/ \|
   3---4

首先，我们创建一个 5 × 5 的矩阵：

    1  2  3  4  5
  ---------------
1|  0  0  0  0  0
2|  0  0  0  0  0
3|  0  0  0  0  0
4|  0  0  0  0  0
5|  0  0  0  0  0

然后，我们按照顺序给顶点编号，并将边的信息填入矩阵中：

    1  2  3  4  5
  ---------------
1|  0  1  1  1  0
2|  1  0  1  1  0
3|  1  1  0  1  0
4|  1  1  1  0  0
5|  0  0  0  0  0

这个矩阵就是该无向图的邻接矩阵表示法。注意，由于是无向图，矩阵是对称的。例如，第 1 行第 2 列和第 2 行第 1 列的值都是 1，表示顶点 1 和顶点 2 之间有一条边。