当前位置：首页 > 《数据结构实验指导书》
第一部分 上机实践
实验四 图
实验时间： 月 日
一、实验目的
1．掌握图的邻接矩阵作为存储结构的方法及其相关操作的实现； 2．掌握图的邻接表作为存储结构的方法及其相关操作的实现； 3．掌握图的最小生树的Prim算法；
4．通过实践掌握图的的拓扑排序、最短路径算法的实现。
二、实验题目与要求
1．实验题目一：图的邻接矩阵存储的实现、图的遍历算法
要求：采用邻接矩阵作为图的存储结构，实现相关基本操作的算法，并进行验证。 2．实验题目二：图的邻接表存储方的实现、图的遍历算法
要求：采用邻接表作为图的存储结构，实现图的创建等操作的算法，并进行验证。在此基础上实现有向图的拓扑排序算法。
3．实验题目三：图最小生成树算法
要求：在题目一或题目二的基础上利用邻接矩阵（或邻接表）作为图的存储结构，编程实现最小生成树求解，并进行验证。
4．图的最短路径算法
要求：在题目一或题目二的基础上利用邻接矩阵（或邻接表）作为图的存储结构，编程实现最短路径算法，并进行验证。
说明：实验题目一、二为必做内容；实验题目三、四为选做内容。
三、实验内容
1．图的邻接矩阵表示法的实现
（1）图的邻接矩阵表示及相关操作的定义。将如下代码设计完整，并保存为“MGraph.h”。
typedef int QElemType; #include \#define INFINITY 9999 #define MaxVexNum 20 typedef struct
{ VexType vexs[MaxVexNum];
int arcs[MaxVexNum][MaxVexNum]; int vexNum,arcNum;
int kind; //图的种类：1-无向图 2-无向网 3-有向图 4-有向网 }MGraph; //图的类型
-27-
第一部分 上机实践
int compareTo(VexType v1,VexType v2);//顶点元素的比较函数声明 int LocateVex(MGraph &G,VexType v)
//在图G中查找顶点v，若存在返回位置，否则返回-1 { int i;
for(i=0;i if(compareTo(G.vexs[i],v)==0) return i; return -1; } void InputVexInfo(VexType v); //顶点信息输入函数声明 void CreatUDG(MGraph &G) //无向图的创建操作 { VexType v1,v2; int i,j,k; G.kind=0; printf(\.vexNum)); printf(\ printf(\ for(i=0;i for(j=0;j printf(\ Start vertex:\ printf(\ End vertex:\ i=LocateVex(G,v1); if(i==-1) { printf(\ return;} j=LocateVex(G,v2); if(j==-1) { printf(\ return;} G.arcs[i][j]=G.arcs[j][i]=1; } } int FirstAdjVex(MGraph &G, int v) //求v的第一个邻接顶点 { //代码略 } int NextAdjVex(MGraph &G, int v,int w) //求v的相对于w的下一个邻接顶点 { //代码略 } void visit(VexType v); //顶点访问函数声明 int visited[MaxVexNum]; //顶点访问辅助数组 void DFS(MGraph &G, int v) //从顶点v出发，深度优先遍历图G -28- 第一部分 上机实践 { //代码略 } void DFSTraverse(MGraph &G) //图的深度优先遍历算法 { //代码略 } void BFSTraverse(MGraph &G) //图的深度优先遍历算法 { //代码略 } （2）图的邻接矩阵表示的测试程序及应用 以下实现了对“MGraph.h”中图的邻接矩阵表示及其操作的测试示例程序。同学们还可自行设计测试程序代码。 #include typedef char VexType[20]; //顶点类型为字符数组类型 #include \ int compareTo(VexType v1,VexType v2)//顶点元素的比较函数定义 { return strcmp(v1,v2); } void InputVexInfo(VexType v) //顶点信息输入函数定义 { scanf(\} void visit(VexType v) //顶点访问函数定义 { printf(\ \} void OutputG(MGraph &G) //图的邻接矩阵的输出操作 { int i,j; printf(\.kind); printf(\ for(i=0;i for(i=0;i -29- 第一部分 上机实践 int main() { MGraph G; CreatUDG(G); OutputG(G); printf(\ DFSTraverse(G); printf(\ BFSTraverse(G); printf(\} （3）完整的程序代码 -30- 搜索更多关于： 《数据结构实验指导书》 的文档
本文作者：...共分享92篇相关文档
