20202330 金晨 实验九 《图》实验报告

课程：《程序设计与数据结构》
班级： 2023
姓名： 金晨
学号：20202330
实验教师：王志强
实验日期：2020年12月15日
必修/选修： 必修

1.实验内容

(1) 初始化：根据屏幕提示（例如：输入1为无向图，输入2为有向图）初始化无向图和有向图（可用邻接矩阵，也可用邻接表），图需要自己定义（顶点个数、边个数，建议先在草稿纸上画出图，然后再输入顶点和边数）（2分）
(2) 图的遍历：完成有向图和无向图的遍历（深度和广度优先遍历）（4分）
(3) 完成有向图的拓扑排序，并输出拓扑排序序列或者输出该图存在环（3分）
(4) 完成无向图的最小生成树（Prim算法或Kruscal算法均可），并输出（3分）
(5) 完成有向图的单源最短路径求解（迪杰斯特拉算法）（3分）

PS：本题12分。目前没有明确指明图的顶点和连通边，如果雷同或抄袭，本次实验0分。

2.实验过程及结果

1.图的初始化

码云链接（1）（2）（3）

邻接表输出

 运行结果：

（1）有向图

 （2）无向图：

2. 图的遍历

 代码链接

 3.拓扑排序

4.无向图的最小生成树（Prim）：

 求图最小生成树的PRIM算法
* 基本思想：假设N=(V,{E})是联通网，TE是N上的最想生成树中的变得集合。算法从U={u0}(u0属于V)，
* TE={}开始，重复执行下述操作：在所有的u属于U，v属于V-U的边（u，v）属于E中找到一条代价最小
* 的边（u0，v0）并入集合TE，同事v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V,{TE})
* 为N的最小生成树。

码云链接

 5.单源最短路径求解（迪杰斯特拉算法）

代码链接

3.其他（感悟、思考等）

　　在学习过程中，我很努力地使自己保持心理的平静，从基础学起，甚至是一些看上去完全没有必要的基础。 我要扎扎实实，一步一个脚印的逐步学习。

  做实验的时候心态炸裂，不过已经是最后一次实验了，耐着性子忍着爆红，一点点改完了代码。结束我持续一天的奋斗