平时刷题发现图论相关的题遇到的比较少，但考场上一旦遇到如果连如何输入、如何存图都不回，那岂不是连骗分的机会的没了，所以写一篇博客记录一下，图的存储方式很多种，这里只针对最常用最简单的邻接矩阵，只有邻接表、链式前向星等各有缺点，且不易理解，大家可以去找别的文章观看

一、邻接矩阵的核心概念

邻接矩阵是用二维数组存储图的结构：

• 对于有 n 个顶点的图，邻接矩阵是 n×n 的数组 g。
• 无权图：g[u][v] = 1 表示 u 和 v 之间有边，0 表示无边。
• 带权图：g[u][v] 存储 u 到 v 的边权（不可达用 INF 表示，如 0x3f3f3f3f）。
• 无向图：邻接矩阵对称（g[u][v] = g[v][u]）；有向图：邻接矩阵非对称。

二、常见输入形式分类

至于如何接收输入根据下面的分类参考我的上一篇I\O大全：输入输出大全

1. 无权无向图（边列表 → 邻接矩阵）

输入：顶点数 n，边数 m，随后 m 行边 (u, v)（顶点编号通常从 1 开始）。
示例输入：

5 6
1 2
1 3
2 3
2 4
3 5
4 5

（5 个顶点，6 条无向边）

2. 无权有向图（边列表 → 邻接矩阵）

输入：顶点数 n，边数 m，随后 m 行有向边 (u, v)。
示例输入：

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

3. 带权无向图（边列表 + 权值 → 邻接矩阵）

输入：顶点数 n，边数 m，随后 m 行边 (u, v, w)（w 为边权）。
示例输入：

3 3
1 2 5
2 3 8
1 3 10

4. 带权有向图（边列表 + 权值 → 邻接矩阵）

输入：顶点数 n，边数 m，随后 m 行有向边 (u, v, w)。
示例输入：

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

5. 直接输入邻接矩阵

输入：顶点数 n，随后 n 行，每行 n 个整数（直接给出 g[u][v] 的值）。
示例输入：

3
0 1 2
1 0 3
2 3 0

三、模板题：邻接矩阵存储 + 深度优先搜索（DFS）遍历

题目：给定无向无权图的邻接矩阵，从顶点 1 出发进行 DFS 遍历，输出遍历顺序。

输入：
第一行是顶点数 n，接下来 n 行，每行 n 个整数（1 表示有边，0 表示无边）。

示例输入：

5
0 1 1 0 0
1 0 1 1 0
1 1 0 0 1
0 1 0 0 1
0 0 1 1 0

输出：DFS 遍历的顶点顺序（如 1 2 3 5 4）。

代码实现：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1005;
int n;              // 顶点数
int g[MAXN][MAXN];  // 邻接矩阵
bool visited[MAXN]; // 标记顶点是否访问过

// 从顶点u出发的DFS
void dfs(int u) {
    visited[u] = true;
    cout << u << " "; // 输出当前顶点
    for (int v = 1; v <= n; ++v) {
        // 若v未访问且u与v有边
        if (!visited[v] && g[u][v] == 1) {
            dfs(v);
        }
    }
}

int main() {
    cin >> n;
    // 读取邻接矩阵
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> g[i][j];
        }
    }
    // 初始化访问标记
    fill(visited, visited + MAXN, false);
    // 从顶点1开始DFS
    dfs(1);
    return 0;
}

四、进阶模板题：邻接矩阵 + Floyd 求全源最短路径

题目：给定带权有向图的邻接矩阵（不可达用 INF 表示），求所有顶点对的最短路径长度。

输入：
第一行是顶点数 n，接下来 n 行，每行 n 个整数（g[i][j] 为边权，INF 表示不可达，顶点自身权为 0）。

示例输入：

4
0 2 5 0x3f3f3f3f
0x3f3f3f3f 0 2 4
0x3f3f3f3f 0x3f3f3f3f 0 1
1 0x3f3f3f3f 0x3f3f3f3f 0

输出：所有顶点对的最短路径矩阵（不可达输出 INF）。

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f; // 表示“无穷大”（不可达）
int n;
int g[MAXN][MAXN];   // 原始邻接矩阵
int dist[MAXN][MAXN];// 存储最短路径

int main() {
    cin >> n;
    // 读取邻接矩阵并初始化dist
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> g[i][j];
            dist[i][j] = g[i][j];
        }
    }
    // Floyd算法：枚举中间点k，更新所有i→j的最短路径
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    // 输出结果
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (dist[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }
    return 0;
}

总结

邻接矩阵的输入需根据 “图的类型（有向 / 无向、带权 / 无权）” 选择不同的读取方式：

• 边列表形式：需先读顶点数、边数，再逐条边填充邻接矩阵。
• 直接矩阵形式：直接读取 n×n 的数组。
  结合 DFS、Floyd 等算法，可完成图的遍历、最短路径等基础任务。