图论是数据结构与算法的核心模块，也是面试高频考点，但很多新手会卡在“概念抽象”“代码难写”“逻辑理不清”三个环节。本文避开复杂理论，从“用代码实现”的角度出发，手把手教你掌握图的两种核心存储结构（邻接矩阵、邻接表），再深入讲解深度优先（DFS）、广度优先（BFS）遍历算法，全程附可直接运行的C语言代码和清晰的执行逻辑，零基础也能跟着敲、跟着懂。
一、先搞懂：图是什么？为什么需要存储结构？
简单来说，图是由“顶点”和“边”组成的数据结构——比如社交网络中，每个人是“顶点”，朋友关系是“边”；地图中，城市是“顶点”，道路是“边”。
但计算机无法直接“理解”顶点和边的关系，必须通过特定的结构存储，这就有了“邻接矩阵”和“邻接表”两种经典方案：
邻接矩阵：用二维数组存，适合顶点少、边多的“稠密图”（比如地图中相邻城市）；
邻接表：用“顶点数组+链表”存，适合顶点多、边少的“稀疏图”（比如社交网络）。
先从最直观的邻接矩阵开始学起，再对比理解邻接表的优势。
二、图的第一种存储结构：邻接矩阵（Adjacency Matrix）
2.1 核心逻辑：用二维数组映射顶点关系
假设图有 n 个顶点，用 n×n 的二维数组 matrix 存储：
matrix[i][j] = 权值 ：表示顶点 i 和顶点 j 之间有边，权值是边的“长度”或“权重”；
matrix[i][j] = 无穷大（INF） ：表示顶点 i 和顶点 j 之间无边；
matrix[i][i] = 0 ：表示顶点自身到自身无边（可选）。
比如一个5顶点的图，邻接矩阵长这样（ ∞ 表示无边）：
plaintext
0 1 2 3 4
0 0 2 3 ∞ ∞
1 2 0 ∞ 1 ∞
2 3 ∞ 0 ∞ 4
3 ∞ 1 ∞ 0 ∞
4 ∞ ∞ 4 ∞ 0
2.2 完整代码实现（可直接运行）
新建 adjacency_matrix.c 文件，复制以下代码，包含“初始化、加边、打印”核心功能：
c
#include <stdio.h>
#include <stdbool.h>
// 配置参数：最大顶点数、无边标识（无穷大）
#define MAX_VERTICES 100
#define INF 999999
// 邻接矩阵结构体：存储顶点和边的关系
typedef struct {
char vertex[MAX_VERTICES]; // 顶点数组（用'0'/'1'/'2'...标识顶点）
int matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵（存边权）
int vertex_num; // 实际顶点数量
} AdjMatrixGraph;
// 1. 初始化邻接矩阵
void initAdjMatrix(AdjMatrixGraph *graph, int n) {
graph->vertex_num = n;
// 初始化顶点：默认用'0'~'n-1'标识（也可自定义为字母，比如'A'）
for (int i = 0; i < n; i++) {
graph->vertex[i] = '0' + i;
}
// 初始化矩阵：无边设为INF，自身设为0
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph->matrix[i][j] = (i == j) ? 0 : INF;
}
}
}
// 2. 添加无向边（v1、v2是顶点索引，weight是边权）
void addEdgeMatrix(AdjMatrixGraph *graph, int v1, int v2, int weight) {
// 先检查顶点索引是否合法（避免越界）
if (v1 < 0 || v1 >= graph->vertex_num || v2 < 0 || v2 >= graph->vertex_num) {
printf("顶点索引错误，添加边失败！\n");
return;
}
// 无向图：边是双向的，所以matrix[v1][v2]和matrix[v2][v1]都要设为weight
graph->matrix[v1][v2] = weight;
graph->matrix[v2][v1] = weight;
}
// 3. 打印邻接矩阵（直观查看图结构）
void printAdjMatrix(AdjMatrixGraph *graph) {
printf("邻接矩阵（INF表示无边）：\n");
// 先打印顶点表头（方便对应）
printf(" ");
for (int i = 0; i < graph->vertex_num; i++) {
printf("%c ", graph->vertex[i]);
}
printf("\n");
// 打印矩阵内容
for (int i = 0; i < graph->vertex_num; i++) {
printf("%c ", graph->vertex[i]);
for (int j = 0; j < graph->vertex_num; j++) {
if (graph->matrix[i][j] == INF) {
printf("∞ ");
} else {
printf("%d ", graph->matrix[i][j]);
}
}
printf("\n");
}
}
// 主函数：测试邻接矩阵
int main() {
AdjMatrixGraph graph;
// 1. 初始化5个顶点的图
initAdjMatrix(&graph, 5);
// 2. 添加无向边（顶点0-1边权2，0-2边权3，1-3边权1，2-4边权4）
addEdgeMatrix(&graph, 0, 1, 2);
addEdgeMatrix(&graph, 0, 2, 3);
addEdgeMatrix(&graph, 1, 3, 1);
addEdgeMatrix(&graph, 2, 4, 4);
// 3. 打印结果
printAdjMatrix(&graph);
return 0;
}
2.3 编译运行步骤（新手必看）
1. 环境准备：确保已安装MinGW（C语言编译器），若未安装，可参考文末“附录”的MinGW安装教程；
2. 保存代码：用VS Code打开文件，按 Ctrl+S 保存为 adjacency_matrix.c ；
3. 编译代码：打开VS Code终端（“终端”→“新建终端”），输入命令：
bash
gcc adjacency_matrix.c -o adjacency_matrix
4. 运行代码：输入命令执行生成的可执行文件：
bash
./adjacency_matrix.exe
5. 查看结果：终端会输出5×5的邻接矩阵，与前文示例一致，说明代码运行成功。
三、图的第二种存储结构：邻接表（Adjacency List）
3.1 核心逻辑：用“顶点数组+链表”节省空间
邻接矩阵的缺点很明显：如果顶点多但边少（比如1000个顶点，只有100条边），二维数组会浪费大量空间（大部分都是 INF ）。
邻接表的解决方案是：
- 顶点数组：存储所有顶点，每个顶点对应一个“链表头”；
- 链表：每个顶点的链表，只存储该顶点的“邻接点”和“边权”，无边的顶点不占空间。
比如同样是5顶点的图，邻接表长这样：
plaintext
0 -> 2(3) -> 1(2) -> NULL
1 -> 3(1) -> 0(2) -> NULL
2 -> 4(4) -> 0(3) -> NULL
3 -> 1(1) -> NULL
4 -> 2(4) -> NULL
3.2 完整代码实现（可直接运行）
新建 adjacency_list.c 文件，复制以下代码，核心是“边节点结构体+顶点结构体+邻接表操作”：
c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100 // 最大顶点数
// 1. 边节点结构体：存储邻接点和边权（链表的每个节点）
typedef struct EdgeNode {
int adjvex; // 邻接点的索引（对应顶点数组的下标）
int weight; // 边的权值
struct EdgeNode *next; // 指向下一个边节点（链表指针）
} EdgeNode;
// 2. 顶点结构体：存储顶点数据和边链表头指针
typedef struct VertexNode {
char data; // 顶点标识（如'0'/'1'）
EdgeNode *firstedge; // 指向边链表的头指针（初始为NULL）
} VertexNode;
// 3. 邻接表结构体：顶点数组+顶点数量
typedef struct {
VertexNode adjlist[MAX_VERTICES]; // 顶点数组
int vertex_num; // 实际顶点数量
int edge_num; // 实际边数量（可选，用于统计）
} AdjListGraph;
// 4. 初始化邻接表
void initAdjList(AdjListGraph *graph, int n) {
graph->vertex_num = n;
graph->edge_num = 0;
// 初始化每个顶点：数据设为'0'~'n-1'，边链表头指针设为NULL
for (int i = 0; i < n; i++) {
graph->adjlist[i].data = '0' + i;
graph->adjlist[i].firstedge = NULL;
}
}
// 5. 添加无向边（v1、v2是顶点索引，weight是边权）
void addEdgeList(AdjListGraph *graph, int v1, int v2, int weight) {
// 检查顶点索引合法性
if (v1 < 0 || v1 >= graph->vertex_num || v2 < 0 || v2 >= graph->vertex_num) {
printf("顶点索引错误，添加边失败！\n");
return;
}
)
