数据结构实验指导(3)

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