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

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

**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. 如何通过邻接矩阵快速判断两个顶点是否互为邻居？