图论入门：从基础到遍历算法

引言在前面的数据结构系列中我们学习了线性结构数组、链表、栈、队列和树形结构二叉树、B 树、哈希表。今天要讲的图是比树更复杂、表达能力更强的非线性结构。如果说树表达的是一对多的层级关系一个文件目录、一个公司组织架构那图表达的就是多对多的网状关系——社交网络中的好友关系、地图上的城市道路、互联网中的路由器连接、编译器中的模块依赖……这些全都是图。图论是数据结构与算法中内容最丰富的领域之一也是面试中的常客。本文作为图系列的第一篇将详细讲解图的基本概念、两种存储方式和两种核心遍历算法。第一部分图的基本概念一、图的定义图Graph是由顶点集合和边集合组成的数据结构。形式化地定义为通俗地说顶点就是图中的点人、城市、任务边就是点之间的连线好友关系、道路、依赖。二、图的分类1. 无向图 vs 有向图2. 带权图 vs 无权图3. 完全图完全图图中每一对顶点之间都有边。图的类型最多边数无向完全图n(n-1)/2有向完全图n(n-1)4. 稀疏图 vs 稠密图类型定义判断标准稀疏图边数远小于 n²|E| n log n稠密图边数接近 n²|E| ≈ n²为什么区分稀疏和稠密因为它们适合不同的存储方式——稀疏图用邻接表省空间稠密图用邻接矩阵更快。三、图的核心术语1. 度Degree2. 路径与回路3. 连通性第二部分图的存储方式一、邻接矩阵用一个 n×n 的二维数组存储顶点之间的连接关系代码实现#define MAX_V 100 typedef struct { int vertexNum; // 顶点数量 int edgeNum; // 边数量 int matrix[MAX_V][MAX_V]; // 邻接矩阵 } GraphMatrix; // 初始化 void initGraph(GraphMatrix* g, int n) { g-vertexNum n; g-edgeNum 0; for (int i 0; i n; i) { for (int j 0; j n; j) { g-matrix[i][j] 0; // 无边 } } } // 添加边无向图 void addEdge(GraphMatrix* g, int u, int v) { g-matrix[u][v] 1; g-matrix[v][u] 1; // 无向图对称 g-edgeNum; } // 添加带权边无向图 void addWeightedEdge(GraphMatrix* g, int u, int v, int w) { g-matrix[u][v] w; g-matrix[v][u] w; g-edgeNum; }邻接矩阵的复杂度操作复杂度判断 u、v 是否有边O(1)获取某个顶点的所有邻居O(n)空间O(n²)添加/删除边O(1)适用场景稠密图边多、需要快速判断两点是否相邻。二、邻接表每个顶点维护一个链表存储它连接的所有邻居。代码实现#include stdio.h #include stdlib.h #define MAX_V 100 // 邻接表的边节点 typedef struct EdgeNode { int adjVertex; // 邻接顶点下标 int weight; // 权重带权图用 struct EdgeNode* next; // 下一条边 } EdgeNode; // 邻接表 typedef struct { EdgeNode* adjList[MAX_V]; // 每个顶点的边链表 int vertexNum; int edgeNum; } GraphList; // 初始化 void initGraphList(GraphList* g, int n) { g-vertexNum n; g-edgeNum 0; for (int i 0; i n; i) { g-adjList[i] NULL; } } // 添加边无向图头插法 void addListEdge(GraphList* g, int u, int v, int w) { // u → v EdgeNode* node (EdgeNode*)malloc(sizeof(EdgeNode)); node-adjVertex v; node-weight w; node-next g-adjList[u]; g-adjList[u] node; // v → u无向图对称 node (EdgeNode*)malloc(sizeof(EdgeNode)); node-adjVertex u; node-weight w; node-next g-adjList[v]; g-adjList[v] node; g-edgeNum; }邻接表的复杂度操作复杂度判断 u、v 是否有边O(degree(u))获取某个顶点的所有邻居O(degree(u))空间O(n e)添加/删除边O(1)三、邻接矩阵 vs 邻接表对比项邻接矩阵邻接表空间O(n²)O(n e)判断 u、v 是否有边O(1)O(degree(u))获取所有邻居O(n)O(degree(u))添加边O(1)O(1)适合场景稠密图稀疏图选择原则边数少用邻接表省空间边数多用邻接矩阵快。实际开发中邻接表更常用因为大多数现实图都是稀疏的。第三部分深度优先搜索DFS一、DFS 的核心思想DFS 一条路走到黑走不通再回头。从起点开始沿着一条路径一直走到最深处然后回溯换一条路继续走。二、DFS 代码实现邻接矩阵int visited[MAX_V]; // DFS 递归实现 void DFS_Matrix(GraphMatrix* g, int v) { visited[v] 1; printf(%c , A v); // 访问顶点 v // 遍历 v 的所有邻居 for (int i 0; i g-vertexNum; i) { if (g-matrix[v][i] ! 0 !visited[i]) { DFS_Matrix(g, i); // 递归访问未访问的邻居 } } } // 遍历整个图处理不连通的情况 void DFS_Traverse(GraphMatrix* g) { // 初始化访问标记 for (int i 0; i g-vertexNum; i) { visited[i] 0; } // 对每个未访问的顶点调用 DFS // 如果图不连通需要多次调用 for (int i 0; i g-vertexNum; i) { if (!visited[i]) { DFS_Matrix(g, i); printf((连通分量结束)\n); } } }三、DFS 代码实现邻接表void DFS_List(GraphList* g, int v) { visited[v] 1; printf(%c , A v); // 遍历 v 的边链表 EdgeNode* p g-adjList[v]; while (p ! NULL) { if (!visited[p-adjVertex]) { DFS_List(g, p-adjVertex); } p p-next; } }四、DFS 的非递归实现用栈模拟递归#include stdbool.h void DFS_NonRecursive(GraphMatrix* g, int start) { int stack[MAX_V]; int top -1; bool visited[MAX_V] {false}; stack[top] start; while (top ! -1) { int v stack[top--]; if (!visited[v]) { visited[v] true; printf(%c , A v); // 将所有未访问的邻居入栈 // 反序入栈以保证和递归顺序一致 for (int i g-vertexNum - 1; i 0; i--) { if (g-matrix[v][i] ! 0 !visited[i]) { stack[top] i; } } } } }递归 vs 非递归实现优点缺点递归代码简洁深度过大可能栈溢出非递归栈不受递归深度限制代码稍复杂第四部分广度优先搜索BFS一、BFS 的核心思想BFS 层层扩散先近后远。从起点开始先访问所有邻居再访问邻居的邻居……逐层向外扩展。二、BFS 代码实现邻接矩阵void BFS_Matrix(GraphMatrix* g, int start) { int queue[MAX_V]; int front 0, rear 0; int visited[MAX_V] {0}; // 起点入队 queue[rear] start; visited[start] 1; while (front rear) { int v queue[front]; // 出队 printf(%c , A v); // 将所有未访问的邻居入队 for (int i 0; i g-vertexNum; i) { if (g-matrix[v][i] ! 0 !visited[i]) { queue[rear] i; visited[i] 1; } } } }三、BFS 代码实现邻接表void BFS_List(GraphList* g, int start) { int queue[MAX_V]; int front 0, rear 0; int visited[MAX_V] {0}; queue[rear] start; visited[start] 1; while (front rear) { int v queue[front]; printf(%c , A v); EdgeNode* p g-adjList[v]; while (p ! NULL) { if (!visited[p-adjVertex]) { queue[rear] p-adjVertex; visited[p-adjVertex] 1; } p p-next; } } }第五部分DFS vs BFS对比项DFSBFS数据结构栈递归/显式栈队列遍历顺序纵向深入横向扩散找到的路径不一定最短一定最短无权图空间O(h)h 为深度O(w)w 为最大宽度适用场景路径存在性、连通分量、环检测最短路径、层序遍历实现递归简单队列简单第六部分完整测试代码#include stdio.h #include stdlib.h #include string.h #include stdbool.h #define MAX_V 100 // 邻接矩阵 typedef struct { int vertexNum; int edgeNum; int matrix[MAX_V][MAX_V]; } GraphMatrix; void initMatrix(GraphMatrix* g, int n) { g-vertexNum n; g-edgeNum 0; for (int i 0; i n; i) for (int j 0; j n; j) g-matrix[i][j] 0; } void addMatrixEdge(GraphMatrix* g, int u, int v) { g-matrix[u][v] 1; g-matrix[v][u] 1; g-edgeNum; } // 邻接表 typedef struct EdgeNode { int adjVertex; struct EdgeNode* next; } EdgeNode; typedef struct { EdgeNode* adjList[MAX_V]; int vertexNum; int edgeNum; } GraphList; void initList(GraphList* g, int n) { g-vertexNum n; g-edgeNum 0; for (int i 0; i n; i) g-adjList[i] NULL; } void addListEdge(GraphList* g, int u, int v) { EdgeNode* node; node (EdgeNode*)malloc(sizeof(EdgeNode)); node-adjVertex v; node-next g-adjList[u]; g-adjList[u] node; node (EdgeNode*)malloc(sizeof(EdgeNode)); node-adjVertex u; node-next g-adjList[v]; g-adjList[v] node; g-edgeNum; } // DFS int visited[MAX_V]; void DFS_Matrix(GraphMatrix* g, int v) { visited[v] 1; printf(%c , A v); for (int i 0; i g-vertexNum; i) if (g-matrix[v][i] !visited[i]) DFS_Matrix(g, i); } void DFS_List(GraphList* g, int v) { visited[v] 1; printf(%c , A v); for (EdgeNode* p g-adjList[v]; p; p p-next) if (!visited[p-adjVertex]) DFS_List(g, p-adjVertex); } // BFS void BFS_Matrix(GraphMatrix* g, int start) { int queue[MAX_V], front 0, rear 0; int vis[MAX_V] {0}; queue[rear] start; vis[start] 1; while (front rear) { int v queue[front]; printf(%c , A v); for (int i 0; i g-vertexNum; i) if (g-matrix[v][i] !vis[i]) { queue[rear] i; vis[i] 1; } } } void BFS_List(GraphList* g, int start) { int queue[MAX_V], front 0, rear 0; int vis[MAX_V] {0}; queue[rear] start; vis[start] 1; while (front rear) { int v queue[front]; printf(%c , A v); for (EdgeNode* p g-adjList[v]; p; p p-next) if (!vis[p-adjVertex]) { queue[rear] p-adjVertex; vis[p-adjVertex] 1; } } } // 测试 int main() { GraphMatrix gm; initMatrix(gm, 5); addMatrixEdge(gm, 0, 1); // A-B addMatrixEdge(gm, 0, 2); // A-C addMatrixEdge(gm, 1, 3); // B-D addMatrixEdge(gm, 2, 3); // C-D addMatrixEdge(gm, 1, 4); // B-E GraphList gl; initList(gl, 5); addListEdge(gl, 0, 1); addListEdge(gl, 0, 2); addListEdge(gl, 1, 3); addListEdge(gl, 2, 3); addListEdge(gl, 1, 4); printf( DFS邻接矩阵\n); memset(visited, 0, sizeof(visited)); DFS_Matrix(gm, 0); printf(\n); printf( DFS邻接表\n); memset(visited, 0, sizeof(visited)); DFS_List(gl, 0); printf(\n); printf( BFS邻接矩阵\n); BFS_Matrix(gm, 0); printf(\n); printf( BFS邻接表\n); BFS_List(gl, 0); printf(\n); return 0; }运行结果注意DFS 的邻接矩阵和邻接表结果可能不同因为遍历邻居的顺序不同但这不影响正确性——两者都是合法的 DFS。总结一、核心概念速查概念含义顶点图中的节点边顶点之间的连接有向图边有方向无向图边无方向带权图边有权重连通图任意两点可达度顶点连接的边数稀疏图边数远小于 n²稠密图边数接近 n²二、存储方式对比方式空间判邻边遍历邻居适用邻接矩阵O(n²)O(1)O(n)稠密图邻接表O(ne)O(degree)O(degree)稀疏图三、DFS vs BFS对比DFSBFS结构栈队列路径不一定最短最短场景连通性、环检测最短路径、层级遍历四、一句话记忆图是顶点和边的集合用邻接矩阵稠密或邻接表稀疏存储。DFS 用栈纵向深入BFS 用队列横向扩散。BFS 能找到无权图的最短路径。