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