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