【考研】图的相关应用算法考点（详细全面，含真题）

前言

在 408 考研中，图的应用算法不是考试重点，了解即可。

但在暨南大学的 848 和 830 考研中，图的相关应用算法是考试的重点，出现在填空题和编写算法题中。有需要的同学自取。

本文算法包括但不限于图的遍历（DFS、BFS）、最小生成树（Kruskal）、最短路径算法（Dijkstra、Floyd）、拓扑排序等等。并对重点内容或需注意的内容进行标红或标下划线。在本文的最后，还有相关习题，源自王道讲解。

可搭配以下链接一起学习：

【考研】栈和队列基础算法代码_住在阳光的心里的博客-CSDN博客

【考研】830 + 848 暨大2012-2022真题易混易错题总结（一）-CSDN博客

【考研】《数据结构》知识点总结.pdf_其它文档类资源-CSDN下载

【2023考研】数据结构常考应用典型例题（含真题）_住在阳光的心里的博客-CSDN博客

如若有需要的，可以从下方链接下载本文：

考研数据结构-图的相关应用算法-其它文档类资源-CSDN文库

目录

前言

一、图的存储结构

（一）邻接矩阵

（二）邻接表

二、图的遍历方式

（一）DFS

（二）BFS（用队列实现，不是递归的算法）

三、最小（代价）生成树

（一）Prim 算法（求稠密网）

（二）Kruskal 算法（求稀疏网）（重点）

四、最短路径算法

（一）Dijkstra 算法（重点）

（二）BFS 算法求解非带权图的单源最短路径问题

（三）Floyd 算法

五、拓扑排序

六、习题

---

一、图的存储结构

（一）邻接矩阵

//邻接矩阵
#define MaxVertexNum 100   //顶点数目的最大值
typedef char VertexType;    //顶点的数据类型
typedef int EdgeType;   //带权图中边上权值的数据类型
 
typedef struct{
    VertexType Vex[MaxVertexNum];    //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];    //邻接矩阵，边表；
    int vexnum, arcnum;    //图的当前顶点数和弧数
}MGraph;

（二）邻接表

//邻接表
#define Max