《数据结构实验指导书》

第一部分 上机实践

实验四 图

实验时间： 月 日

一、实验目的

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 #include #include \ #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-