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(度)）效率低。

例题一：图的访问与存储

【题目描述】

给出 N 个点，M 条边的有向图，k 次询问，对于每次询问，求 (x,y) 表示从点 x 出发能否抵达 y。

【输入描述】

第 1 行 3 个整数 N,M,K，表示点数、边数以及询问次数。

接下来 M 行，每行 2 个整数 Ui,Vi，表示边 (Ui,Vi)。点用 1,2,…,N 编号。

接下来 K 行，每行 2 个整数 X,Y，表示询问 (X,Y)。

【输出描述】

共 K 行，对应每次询问的结果，能抵达输出 Yes 否则输出 No。

【样例输入】

4 3 2  1 2  2 4  4 3  1 3  4 1

【样例输出】

Yes  No

【参考答案】

#include <iostream>  #include <cstring>  using namespace std;    const int MAXN = 1005; // 最大顶点数，根据题目约束设置  bool reach[MAXN][MAXN]; // 可达性矩阵，reach[i][j]表示i能否到达j    int main() {      int N, M, K;      cin >> N >> M >> K;            // 初始化可达性矩阵      memset(reach, false, sizeof(reach));      // 每个顶点到自身是可达的      for (int i = 1; i <= N; i++) {          reach[i][i] = true;      }            // 读取边信息，构建邻接矩阵表示的直接可达关系      for (int i = 0; i < M; i++) {          int u, v;          cin >> u >> v;          reach[u][v] = true; // 有向边u->v，所以u直接可达v      }            // Floyd算法预处理所有点对的可达性      // 核心思想：如果i能到k，且k能到j，则i能到j      for (int k = 1; k <= N; k++) {          for (int i = 1; i <= N; i++) {              for (int j = 1; j <= N; j++) {                  if (reach[i][k] && reach[k][j]) {                      reach[i][j] = true;                  }              }          }      }            // 处理查询      for (int i = 0; i < K; i++) {          int x, y;          cin >> x >> y;          if (reach[x][y]) {              cout << "Yes" << endl;          } else {              cout << "No" << endl;          }      }            return 0;  }

【说明】

使用二维布尔数组 reach[MAXN][MAXN] 作为邻接矩阵，同时存储可达性信息

reach[i][j] = true 表示从顶点 i 可以到达顶点 j

这是一种动态规划算法，通过中间顶点来更新可达性

外层循环 k 表示中间顶点，内层循环 i 和 j 表示起点和终点

如果 i 能到达 k，且 k 能到达 j，那么 i 就能到达 j

5.图的输入方式

方式一：给顶点、边数、每条边的信息

先告诉你图有 n 个顶点、m 条边，然后 m 行每行给一条边（起点、终点、权重，无权图默认权重 1）。

比如：

5 4  // 5个顶点（0-4），4条边  0 1  // 边0-1  0 4  // 边0-4  1 2  // 边1-2  2 3  // 边2-3

那么对应代码（临接矩阵）

#include <iostream>  #include <vector>  #include <cstring>  // 用于memset  using namespace std;  const int MAXN = 100;  // 假设顶点数不超过100  int main() {      int n, m;  // n：顶点数，m：边数      //vector<vector<int>> graph(MAXN, vector<int>(MAXN, 0));  // C++风格的二维向量      int graph[MAXN][MAXN];      memset(graph, 0, sizeof(graph));  	// 1. 读入顶点数和边数      cin >> n >> m;      // 2. 读入m条边，填充邻接矩阵      for (int i = 0; i < m; i++) {          int u, v;  // 起点u，终点v          cin >> u >> v;          // 无向图：双向赋值          graph[u][v] = 1;          graph[v][u] = 1;                    // 如果是有向图，只写：graph[u][v] = 1;          // 如果是带权图，读入权重w，赋值为：graph[u][v] = w;      }            // 验证：打印邻接矩阵      cout << "邻接矩阵：" << endl;      for (int i = 0; i < n; i++) {          for (int j = 0; j < n; j++) {              cout << graph[i][j] << " ";          }          cout << endl;      }            return 0;  }

方式二：每个顶点后跟其邻接顶点

部分题目会按 “顶点 + 邻接顶点列表” 输入 —— 先给顶点数 n，然后 n 行，每行先给一个顶点 u，再跟若干个与 u 相邻的顶点（直到结束符，比如 - 1

比如：

5  // 5个顶点  0 1 4 -1  // 顶点0的邻接顶点：1、4  1 0 2 -1  // 顶点1的邻接顶点：0、2  2 1 3 -1  // 顶点2的邻接顶点：1、3  3 2 -1    // 顶点3的邻接顶点：2  4 0 -1    // 顶点4的邻接顶点：0

参考代码

#include <stdio.h>  #include <string.h>    #define MAXN 100    int main() {      int n;      int graph[MAXN][MAXN];      memset(graph, 0, sizeof(graph));            // 1. 读入顶点数      scanf("%d", &n);            // 2. 逐行读每个顶点的邻接顶点      for (int i = 0; i < n; i++) {          int u, v;          scanf("%d", &u);  // 先读当前顶点u                    // 循环读u的邻接顶点v，直到读到-1结束          while (1) {              scanf("%d", &v);              if (v == -1) break;  // 结束符                            graph[u][v] = 1;  // 无向图，双向赋值              graph[v][u] = 1;          }      }            // 打印验证      printf("邻接矩阵：\n");      for (int i = 0; i < n; i++) {          for (int j = 0; j < n; j++) {              printf("%d ", graph[i][j]);          }          printf("\n");      }            return 0;  }

方式三：直接输入邻接矩阵（极少，但偶尔出现）

比如

5  // 顶点数  0 1 0 0 1  // 第0行（顶点0的邻接关系）  1 0 1 0 0  // 第1行（顶点1的邻接关系）  0 1 0 1 0  // 第2行（顶点2的邻接关系）  0 0 1 0 0  // 第3行（顶点3的邻接关系）  1 0 0 0 0  // 第4行（顶点4的邻接关系）

参考代码：

#include <stdio.h>  #include <string.h>    #define MAXN 100    int main() {      int n;      int graph[MAXN][MAXN];      memset(graph, 0, sizeof(graph));            // 1. 读入顶点数      scanf("%d", &n);            // 2. 读入n行，每行n个数字（邻接矩阵）      for (int i = 0; i < n; i++) {          for (int j = 0; j < n; j++) {              scanf("%d", &graph[i][j]);          }      }            // 直接用矩阵做后续操作（比如查询边、计算度等）      printf("顶点0的度：%d\n", graph[0][1] + graph[0][4]);  // 无向图度=邻接边数            return 0;  }