1. 什么是邻接矩阵？

邻接矩阵是图的一种最基础的存储表示方法。它使用一个二维数组（即矩阵）来表示图中各个顶点之间的邻接关系。

对于一个有 n 个顶点的图，其邻接矩阵是一个 n x n 的方阵，我们通常称之为 A。

2. 矩阵元素的定义

矩阵中每个元素 A[i][j] 的值，表示顶点 i 与顶点 j 之间的关系。这个关系的具体含义根据图的类型有所不同：

对于无向图

1. A[i][j] = 1：表示顶点 i 和顶点 j 之间有一条边相连。

2. A[i][j] = 0：表示顶点 i 和顶点 j 之间没有边相连。

重要特性：无向图的邻接矩阵是一个对称矩阵，即 A[i][j] = A[j][i]。因为边 (i, j) 和边 (j, i) 是等同的。

对于有向图

1. A[i][j] = 1：表示存在一条从顶点 i 指向顶点 j 的弧（有向边）。

2. A[i][j] = 0：表示没有从顶点 i 指向顶点 j 的弧。

重要特性：有向图的邻接矩阵不一定对称。A[i][j] = 1 并不保证 A[j][i] = 1。

对于带权图（网络）

1. A[i][j] = w：表示顶点 i 和顶点 j 之间的边的权重为 w（如果存在边）。

2. A[i][j] = 0 或 ∞：表示顶点 i 和顶点 j 之间没有边。通常，我们用一个很大的数（如 ∞）或一个特殊值（如 0，但这可能与零权边冲突）来表示不存在的边，具体取决于算法设计。更常见的做法是：对角线上为0（自己到自己的距离为0），不存在的边用 ∞ 表示。

3. 具体示例

示例1：无向图

假设我们有如下无向图，包含4个顶点 (V0, V1, V2, V3)：

(V0) —— (V1)   |  \     |   |   \    |   |    \   |  (V2) —— (V3)

其邻接矩阵为：

观察：

• 矩阵沿主对角线对称。

• 主对角线上的元素都是0，因为我们通常不考虑顶点自身到自身的边（自环）。

示例2：有向图

假设我们有如下有向图：

(V0) ———> (V1)    ^        |    |        |    |        v  (V3) <——— (V2)

其邻接矩阵为：

观察：

• 矩阵不对称。例如，A[0][1]=1（V0->V1），但 A[1][0]=0（V1->V0不存在）。

4. 邻接矩阵的性质与特点

优点

1. 直观易懂：结构简单，易于理解和实现。

2. 快速判断邻接关系：可以在 O(1) 的时间复杂度内判断任意两个顶点 i 和 j 之间是否存在边，只需检查 A[i][j] 的值即可。

3. 便于计算：很多基于矩阵运算的图算法（如通过计算矩阵的幂来求路径数量）非常方便。

4. 适合稠密图：当图的边数接近顶点数的平方时（即稠密图），空间利用率高。

缺点

1. 空间复杂度高：空间复杂度为 O(n²)，其中 n 是顶点数。对于一个有1000个顶点的稀疏图（边数很少），也需要一个100万元素的矩阵，其中大部分是0，造成空间浪费。

2. 添加/删除顶点效率低：添加或删除一个顶点需要改变整个矩阵的大小，操作代价高。

3. 遍历邻接点效率低：要找出一个顶点的所有邻接点，需要扫描对应的一整行，时间复杂度为 O(n)。对于稀疏图，这比邻接表（时间复杂度 O(度)）效率低。

代码实现：

#include <iostream>  #include <vector>  #include <climits>  using namespace std;    // 全局变量存储图的核心信息  vector<vector<int>> adjMatrix;  // 邻接矩阵  int numVertices;                // 顶点数量  bool isDirected;                // 是否为有向图  int INF = INT_MAX;              // 无边连接的标记    // 初始化图  void initGraph(int n, bool directed = false, int inf = INT_MAX) {      numVertices = n;      isDirected = directed;      INF = inf;      // 初始化矩阵：n×n，对角线为0，其余为INF      adjMatrix.resize(n, vector<int>(n, INF));      for (int i = 0; i < n; ++i) {          adjMatrix[i][i] = 0;      }  }    // 添加边  void addEdge(int from, int to, int weight = 1) {      if (from < 0 || from >= numVertices || to < 0 || to >= numVertices) {          cerr << "顶点索引越界！" << endl;          return;      }      adjMatrix[from][to] = weight;      if (!isDirected) {  // 无向图添加反向边          adjMatrix[to][from] = weight;      }  }    // 删除边  void removeEdge(int from, int to) {      if (from < 0 || from >= numVertices || to < 0 || to >= numVertices) {          cerr << "顶点索引越界！" << endl;          return;      }      adjMatrix[from][to] = INF;      if (!isDirected) {  // 无向图删除反向边          adjMatrix[to][from] = INF;      }  }    // 获取边的权值  int getWeight(int from, int to) {      if (from < 0 || from >= numVertices || to < 0 || to >= numVertices) {          cerr << "顶点索引越界！" << endl;          return -1;      }      return adjMatrix[from][to];  }    // 打印邻接矩阵  void printAdjMatrix() {      cout << "邻接矩阵（" << (isDirected ? "有向图" : "无向图") << "）：" << endl;      // 打印列索引      cout << "   ";      for (int i = 0; i < numVertices; ++i) {          cout << i << "  ";      }      cout << endl;      // 打印每行数据      for (int i = 0; i < numVertices; ++i) {          cout << i << "  ";          for (int j = 0; j < numVertices; ++j) {              if (adjMatrix[i][j] == INF) {                  cout << "∞  ";              } else {                  cout << adjMatrix[i][j] << "  ";              }          }          cout << endl;      }  }      int main() {      // 测试无向无权图      cout << "===== 无向无权图 =====" << endl;      initGraph(4);  // 4个顶点，默认无向图      addEdge(0, 1);      addEdge(0, 2);      addEdge(1, 2);      addEdge(1, 3);      addEdge(2, 3);      printAdjMatrix();        // 测试有向带权图      cout << "\n===== 有向带权图 =====" << endl;      initGraph(3, true);  // 3个顶点，有向图      addEdge(0, 1, 5);      addEdge(1, 2, 3);      addEdge(2, 0, 2);      printAdjMatrix();        // 测试删除边      cout << "\n删除有向图中1->2的边后：" << endl;      removeEdge(1, 2);      printAdjMatrix();        return 0;  }