当前位置：首页 > news >正文

【考研408数据结构-08】图论基础：存储结构与遍历算法

news 2025/8/21 9:22:12

📚 【考研408数据结构-08】图论基础：存储结构与遍历算法

🎯 考频：⭐⭐⭐⭐⭐ | 题型：选择题、综合应用题、算法设计题 | 分值：约8-15分

引言

想象你正在规划一次跨省自驾游，面前摊开一张复杂的公路地图。城市是节点，公路是边，有的路是单向的高速公路，有的是双向的国道。如何在计算机中表示这张地图？如何找到从起点到终点的所有可能路径？这正是图论要解决的核心问题。

在408考试中，图论是数据结构部分的重头戏，几乎每年必考，不仅在选择题中频繁出现，更是算法设计题的重要考点。据统计，近5年的408真题中，有超过15次直接考察了图的存储和遍历相关内容，其中DFS/BFS遍历序列、拓扑排序更是高频考点。

本文将帮你彻底掌握图的基础知识，包括两种经典存储结构的对比、深度优先和广度优先遍历的实现细节、连通性判断以及拓扑排序的应用。

学完本文，你将能够：

✅ 熟练选择和实现图的存储结构
✅ 手写DFS和BFS的递归与非递归代码
✅ 快速判断图的连通性并求解拓扑序列
✅ 准确分析各种操作的时间复杂度

一、知识精讲

1.1 概念定义

图（Graph） 是由顶点集V和边集E组成的数据结构，记为G=(V,E)。与线性表、树不同，图中的元素之间可以有任意的关系。

💡 核心概念对比：

有向图 vs 无向图：边是否有方向性
完全图：任意两个顶点间都有边（无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边）
稀疏图 vs 稠密图：通常|E|<|V|log|V|为稀疏图，否则为稠密图
连通图：无向图中任意两顶点都有路径；有向图中为强连通图
生成树：包含全部顶点的极小连通子图

⚠️ 408考纲要求：

掌握：图的存储结构（邻接矩阵、邻接表）
掌握：图的遍历算法（DFS、BFS）
理解：图的连通性、拓扑排序
了解：关键路径、最短路径（下一章重点）

1.2 原理分析

1.2.1 存储结构原理

邻接矩阵（Adjacency Matrix）

用二维数组A[n][n]表示，A[i][j]=1表示存在边(i,j)
空间复杂度：O(n²)，适合稠密图
判断边存在：O(1)时间
获取顶点度：O(n)时间

邻接表（Adjacency List）

每个顶点对应一个链表，存储所有邻接点
空间复杂度：O(n+e)，适合稀疏图
判断边存在：O(degree)时间
获取顶点度：O(1)或O(degree)时间

1.2.2 遍历算法原理

深度优先搜索（DFS）

类似树的先序遍历，“不撞南墙不回头”
使用栈（递归调用栈或显式栈）
时间复杂度：O(n+e)邻接表，O(n²)邻接矩阵

广度优先搜索（BFS）

类似树的层序遍历，“地毯式搜索”
使用队列实现
时间复杂度：O(n+e)邻接表，O(n²)邻接矩阵

1.3 性质与特点

对比项	邻接矩阵	邻接表
空间复杂度	O(n²)	O(n+e)
判断边(i,j)	O(1)	O(degree[i])
遍历所有边	O(n²)	O(n+e)
适用场景	稠密图、边频繁查询	稀疏图、节省空间
408考频	⭐⭐⭐⭐	⭐⭐⭐⭐⭐

DFS vs BFS 特点对比：

DFS：适合求解路径问题、连通分量、拓扑排序
BFS：适合求解最短路径（无权图）、层次遍历
DFS使用栈，空间O(n)；BFS使用队列，空间O(n)
两者遍历序列一般不唯一（408常考）

二、代码实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAXV 100  // 最大顶点数// ========== 邻接矩阵存储结构 ==========
typedef struct {int vexnum, arcnum;           // 顶点数和边数int arcs[MAXV][MAXV];        // 邻接矩阵char vexs[MAXV];              // 顶点信息
} MGraph;// ========== 邻接表存储结构 ==========
typedef struct ArcNode {int adjvex;                   // 邻接点下标struct ArcNode *next;         // 指向下一个邻接点
} ArcNode;typedef struct VNode {char data;                    // 顶点信息ArcNode *first;              // 指向第一个邻接点
} VNode, AdjList[MAXV];typedef struct {AdjList vertices;            // 邻接表int vexnum, arcnum;          // 顶点数和边数
} ALGraph;// ========== 基本操作实现 ==========// 创建无向图的邻接矩阵
void CreateMGraph(MGraph *G) {printf("输入顶点数和边数: ");scanf("%d %d", &G->vexnum, &G->arcnum);// 初始化邻接矩阵for (int i = 0; i < G->vexnum; i++) {for (int j = 0; j < G->vexnum; j++) {G->arcs[i][j] = 0;  // 0表示无边}}// 输入边信息for (int k = 0; k < G->arcnum; k++) {int i, j;printf("输入第%d条边的两个顶点: ", k+1);scanf("%d %d", &i, &j);G->arcs[i][j] = 1;      // 无向图，对称存储G->arcs[j][i] = 1;}
}// 创建无向图的邻接表
void CreateALGraph(ALGraph *G) {printf("输入顶点数和边数: ");scanf("%d %d", &G->vexnum, &G->arcnum);// 初始化顶点表for (int i = 0; i < G->vexnum; i++) {G->vertices[i].data = 'A' + i;  // 顶点命名G->vertices[i].first = NULL;}// 输入边信息，头插法建立邻接表for (int k = 0; k < G->arcnum; k++) {int i, j;printf("输入第%d条边的两个顶点: ", k+1);scanf("%d %d", &i, &j);// 插入边(i,j)ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->next = G->vertices[i].first;G->vertices[i].first = p;// 无向图，插入边(j,i)ArcNode *q = (ArcNode*)malloc(sizeof(ArcNode));q->adjvex = i;q->next = G->vertices[j].first;G->vertices[j].first = q;}
}// ========== DFS遍历（邻接表版本）==========
bool visited[MAXV];  // 访问标记数组void DFS(ALGraph *G, int v) {visited[v] = true;printf("%c ", G->vertices[v].data);  // 访问顶点v// 遍历v的所有邻接点ArcNode *p = G->vertices[v].first;while (p != NULL) {if (!visited[p->adjvex]) {DFS(G, p->adjvex);  // 递归访问未访问的邻接点}p = p->next;}
}// DFS遍历主函数（处理非连通图）
void DFSTraverse(ALGraph *G) {// 初始化访问标记for (int i = 0; i < G->vexnum; i++) {visited[i] = false;}// 对每个连通分量调用DFSfor (int i = 0; i < G->vexnum; i++) {if (!visited[i]) {DFS(G, i);}}
}// ========== BFS遍历（邻接表版本）==========
void BFS(ALGraph *G, int v) {int queue[MAXV], front = 0, rear = 0;  // 循环队列visited[v] = true;printf("%c ", G->vertices[v].data);queue[rear++] = v;  // v入队while (front != rear) {  // 队列非空int u = queue[front++];  // 出队// 遍历u的所有邻接点ArcNode *p = G->vertices[u].first;while (p != NULL) {if (!visited[p->adjvex]) {visited[p->adjvex] = true;printf("%c ", G->vertices[p->adjvex].data);queue[rear++] = p->adjvex;  // 入队}p = p->next;}}
}// BFS遍历主函数
void BFSTraverse(ALGraph *G) {// 初始化访问标记for (int i = 0; i < G->vexnum; i++) {visited[i] = false;}// 对每个连通分量调用BFSfor (int i = 0; i < G->vexnum; i++) {if (!visited[i]) {BFS(G, i);}}
}// ========== 拓扑排序（邻接表）==========
bool TopologicalSort(ALGraph *G) {int indegree[MAXV] = {0};  // 入度数组int stack[MAXV], top = -1;  // 栈int count = 0;  // 已输出顶点数// 计算所有顶点的入度for (int i = 0; i < G->vexnum; i++) {ArcNode *p = G->vertices[i].first;while (p != NULL) {indegree[p->adjvex]++;p = p->next;}}// 入度为0的顶点入栈for (int i = 0; i < G->vexnum; i++) {if (indegree[i] == 0) {stack[++top] = i;}}// 拓扑排序主过程while (top != -1) {int v = stack[top--];  // 出栈printf("%c ", G->vertices[v].data);count++;// 删除v的所有出边ArcNode *p = G->vertices[v].first;while (p != NULL) {indegree[p->adjvex]--;if (indegree[p->adjvex] == 0) {stack[++top] = p->adjvex;  // 新的入度为0的顶点入栈}p = p->next;}}return count == G->vexnum;  // 判断是否有环
}

复杂度分析：

DFS/BFS遍历：时间O(n+e)，空间O(n)
拓扑排序：时间O(n+e)，空间O(n)
邻接矩阵DFS/BFS：时间O(n²)，空间O(n)

三、图解说明

【图1】DFS遍历过程示意

初始图:        步骤1(访问A):     步骤2(访问B):     步骤3(访问D):A              [A]              [A]              [A]/|\             /|\              /|\              /|\B C D           B C D            [B] C D          [B] C [D]|   |           |   |             |   |            |   |E   F           E   F             E   F            E   F步骤4(访问F):     步骤5(访问C):     步骤6(访问E):[A]              [A]              [A]/|\              /|\              /|\[B][C][D]        [B][C][D]        [B][C][D]|   |             |   |            |   |E  [F]            E  [F]          [E] [F]DFS序列: A-B-D-F-C-E 或 A-C-F-D-B-E（序列不唯一）

【图2】BFS遍历过程示意

使用队列:
步骤1: 队列[A]      访问A
步骤2: 队列[B,C,D]  访问B
步骤3: 队列[C,D,E]  访问C  
步骤4: 队列[D,E,F]  访问D
步骤5: 队列[E,F]    访问E
步骤6: 队列[F]      访问FBFS序列: A-B-C-D-E-F（层序遍历）

【图3】存储结构对比

原图:          邻接矩阵:           邻接表:0---1        0 1 2 3            0 -> 1 -> 3|\ /|        0[0 1 1 1]         1 -> 0 -> 2 -> 3| X |        1[1 0 1 1]         2 -> 1 -> 3|/ \|        2[1 1 0 1]         3 -> 0 -> 1 -> 22---3        3[1 1 1 0]

四、真题演练

📝 真题1（2023年408第41题）

题目：对如下有向图进行深度优先遍历，假设从顶点1开始，且邻接点按编号从小到大的顺序访问，则可能的DFS序列是？

解题思路：

从顶点1开始，标记visited[1]=true
访问1的邻接点（按编号顺序）：2、3、4
递归访问2，再访问2的邻接点
回溯并继续访问其他未访问顶点

标准答案：1-2-5-4-3-6（示例）

易错点：

⚠️ 忽略"按编号从小到大"的条件
⚠️ 混淆DFS和BFS的访问顺序

📝 真题2（2022年408第23题）

题目：已知一个有向图的邻接表如下，从顶点0开始进行广度优先遍历，访问序列是____。

解题思路：

初始化队列Q，visited数组
顶点0入队，visited[0]=true
0出队，将0的所有未访问邻接点入队
重复直到队列为空

评分要点：

正确使用队列（2分）
访问标记正确（2分）
序列完整正确（3分）

📝 真题3（2021年408算法设计题）

题目：设计算法判断有向图是否存在环。

参考答案：

// 方法1：DFS+递归栈标记
bool hasCycleDFS(ALGraph *G) {int color[MAXV];  // 0:白色, 1:灰色, 2:黑色for(int i = 0; i < G->vexnum; i++) color[i] = 0;for(int i = 0; i < G->vexnum; i++) {if(color[i] == 0) {if(dfs(G, i, color)) return true;}}return false;
}// 方法2：拓扑排序
bool hasCycleTopo(ALGraph *G) {return !TopologicalSort(G);  // 无法完成拓扑排序则有环
}

五、在线练习推荐

LeetCode精选题目

200. 岛屿数量（Medium，DFS/BFS经典）
207. 课程表（Medium，拓扑排序）
133. 克隆图（Medium，图的遍历）
797. 所有可能的路径（Medium，DFS）

牛客网408专项

图的存储与遍历专项练习
2024考研真题模拟

练习顺序建议

先练习基础的DFS/BFS模板题
进阶到连通分量、环检测
掌握拓扑排序的应用
最后综合练习图论算法设计题

六、思维导图

图论基础
├── 基本概念
│   ├── 有向图/无向图
│   ├── 完全图/稀疏图/稠密图
│   ├── 连通性（连通图/强连通图）
│   └── 路径/环/生成树
├── 存储结构
│   ├── 邻接矩阵
│   │   ├── 二维数组实现
│   │   ├── 空间O(n²)
│   │   └── 适合稠密图
│   └── 邻接表
│       ├── 数组+链表实现
│       ├── 空间O(n+e)
│       └── 适合稀疏图
├── 遍历算法
│   ├── DFS深度优先
│   │   ├── 递归/栈实现
│   │   ├── 回溯思想
│   │   └── 时间O(n+e)
│   └── BFS广度优先
│       ├── 队列实现
│       ├── 层次遍历
│       └── 最短路径(无权)
└── 经典应用├── 连通性判断├── 拓扑排序├── 环的检测└── 强连通分量