37
2. 完成源文件的编写，对mgraph.h里的函数进行测试。graph.cpp主要含main()函数的实现。
3. 编译运行。
B E
A C G D F
38
实验6 图的简单应用
实验目的
1. 掌握图的最短路径概念。
2. 掌握生成最小生成树的Prim算法（用邻接矩阵表示图）/克鲁斯卡尔算法。 3. 理解求最短路径的DijKstra算法（用邻接矩阵表示图）。
实验要求
1． 独立完成；
2． 程序调试正确，有执行结果。
实验内容（基础题必做，应用题任选）
1、基础题
编写用邻接矩阵表示有向带权图时图的基本操作的实现函数，主要包括： ① 初始化邻接矩阵表示的有向带权图
② 建立邻接矩阵表示的有向带权图 （即通过输入图的每条边建立图的邻接
矩阵）
③ 输出邻接矩阵表示的有向带权图（即输出图的每条边）。
④ 编写求最短路径的DijKstra算法函数 void Dijkstra( adjmatrix GA,
int dist[], edgenode *path[], int i, int n) ，该算法求从顶点i到其余顶点的最短路径与最短路径长度，并分别存于数组 path 和 dist 中。（可选）
⑤ 编写打印输出从源点到每个顶点的最短路径及长度的函数 void
PrintPath(int dist[], edgenode *path[], int n)。（可选） 同时建立一个验证操作实现的主函数进行测试。 2、应用题
编写Prim算法函数 void Prim(adjmatrix G, edgset CT, int n)或者克鲁斯卡尔算法函数以及输出边集数组的函数 void PrintEdge(edgeset CT, int n)。编写主函数测试生成最小生成树并输出（即输出边集）。 测试数据如下： 0 5
4 10 6 9 1 12 2 2 5
7 8 3 3 15 6 39
实验步骤参考：
1.完成头文件的编写。graph.h主要含结构体的定义和函数的实现。
40
相关推荐：
loading