实验六 图的创建及应用(I)

1、姓名学号实验项目图的创建及应用（I）实验内容1编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接矩阵和邻接表存储结构并输出显示。（题集150页5.3扩充）存储结构定义分别参见教材第161页和第163页。2试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（ij）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。（题集第49页7.27）算法设计与程序实现：算法分析 本次实验主函数采用循环选择结构，主函数调用自己编写的头文件DataStructure_Graph.h中的相关功能函数，完成实验要求。 主程序结构

2、：1、邻接矩阵表示法： 1、创建有向图； /调用CreateGraph(MG)创建有向图2、显示图信息； /调用DisplayGraph(MG) 显示图信息3、返回上一界面；2、邻接表表示法：1、创建有向图； /调用CreateGraph(ALG)创建有向图2、显示图信息；/调用DisplayGraph(ALG) 显示图信息3、返回上一界面；3、基于深度优先搜索判断是否存在指定位置的路径：1、使用已创建的邻接表表示的图进行搜索判断;/调用exist_path_DFS(ALG, i, j)搜索2、创建新的图进行搜索判断；/创建新的有向图，并调用exist_path_DFS(R_ALG, i, j

3、)搜索3、返回上一界面；4、退出程序 创建图的算法分析Ø 邻接矩阵结构创建图：首先由键盘输入待创建的图的顶点数，弧数以及是否含有弧信息，然后由顶点数控制循环构造顶点向量,接着由顶点数控制循环初始化邻接矩阵(adj=0,info=NUll)，再次输入弧信息，此时将输入的弧的弧头和弧尾与顶点信息进行匹配，从而确定弧在邻接矩阵中的位置(有弧时为1)，如果输入的弧有信息的话，在进行有无弧的判断写邻接矩阵时进行绑定，有键盘输入即可。Ø 邻接表结构创建图：首先由键盘输入待创建的图的顶点数，弧数，然后由顶点数控制循环初始化顶点信息(顶点数据信息及顶点第一条弧指针(firstarc = N

4、ULL),接着由弧数控制循环输入弧头和弧尾顶点，与之前建立的顶点信息进行匹配，从而确定弧头和弧尾的位置信息，此时生成一个弧结点类型的存储空间，采用单链表中在表头插入新结点的方法，将弧的信息插入到顶点的第一条弧之后，如同此法，对每个顶点都进行以上操作，这就建立了图的邻接表结构。深度优先搜索判断是否存在指定位置的路径算法分析首先判断指定的两个位置向量是否相等，如果相等，则肯定有路径相连，否则从指定的弧头结点开始搜索，将该顶点访问过的弧的访问标志置1，任何到该弧的弧头顶点进行如上操作，当搜索该顶点的所有弧都没有找到则返回0，然后返回上一顶点，对该顶点的其他弧进行访问。当指定顶点的所有弧都被搜索访问过

5、都没有找到，此时程序返回0。核心程序此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释处，核心程序如下：1.主函数如下：#include "iostream" /输入输出流库头文件#include "fstream" /文件操作流库头文件#include "windows.h" /cmd窗口设置函数头文件#include "ADT.h" /数据结构中相关结构体类型定义及相关数据类型定义#include "DataStructure_Graph.h" /数据结

6、构第七章图相关函数的定义及声明using namespace std;void main_menu(void);void minor_menu1(void);void minor_menu2(void);void minor_menu3(void);int main(void)system("title 数据结构实验 实验六：图的创建及应用（I）"); /设置cmd窗口标题system("color F1"); /设置控制台窗口的背景色和前景色system("date /T"); /输出当前的日期while (1)main_menu(

7、); /主菜单显示MGraph MG; /邻接矩阵表示图ALGraph ALG; /邻接表表示图ALGraph &G = ALG;char ch; /主菜单输入选择 cout << ">请选择功能： "cin >> ch;switch (ch)case '1':system("cls");while (1)minor_menu1(); /二级菜单显示char ch1; /二级菜单输入选择 cout << endl << ">请选择功能："cin >

8、;> ch1;switch (ch1)case '1': /创建有向图system("cls");CreateGraph(MG);cout << "操作完毕！" << endl;system("pause");system("cls");continue;case '2': /显示图信息system("cls");DisplayGraph(MG);cout << "操作完毕！" << end

9、l;system("pause");system("cls");continue;case '3': /返回上一界面break;default:system("cls");cout << "输入错误，请重新输入！" << endl;continue;system("cls");break;break;case'2':system("cls");while (1)minor_menu2();char ch1;/二层菜单输入

10、选择 cout << endl << ">请选择功能："cin >> ch1;switch (ch1)case '1':/创建图信息system("cls");CreateGraph(ALG);cout << "操作完毕！" << endl;system("pause");system("cls");continue;case '2':/显示图信息system("cls");Di

11、splayGraph(ALG);cout << "操作完毕！" << endl;system("pause");system("cls");continue;case'3': /返回上一界面break;default:system("cls");cout << "输入错误，请重新输入！" << endl;continue;system("cls");break;break;case '3':sys

12、tem("cls");while (1)minor_menu3();ALGraph R_ALG;int i, j; /待搜索的顶点的位置char ch1; /二层菜单输入选择 cout << endl << ">请选择功能："cin >> ch1;switch (ch1)case '1':/使用已创建的邻接表表示的图进行搜索system("cls");cout << "请输入待搜索的顶点v(i) 顶点v(j)(以空格分隔)："cin >&g

13、t; i>> j;int flag = exist_path_DFS(G, i, j);if (flag)cout << "搜索成功！存在顶点v(i):" << G.verticesi.data << "顶点v(j):" << G.verticesj.data << "的路径" << endl;elsecout << "搜索失败！不存在顶点v(i):" << G.verticesi.data <<

14、 "到顶点v(j):" << G.verticesj.data << "的路径" << endl;cout << "操作完毕！" << endl;system("pause");system("cls");continue;case '2': /创建新图进行搜索system("cls");CreateGraph(R_ALG);cout << "请输入待搜索的顶点v(i) 顶点v(

15、j)(以空格分隔)："cin >> i >> j;int flag = exist_path_DFS(R_ALG, i, j);if (flag)cout << "搜索成功！存在顶点v(i):" << R_ALG.verticesi.data << "到顶点v(j):" << R_ALG.verticesj.data << "的路径" << endl;elsecout << "搜索失败！不存在顶点v(i):&

16、quot; << R_ALG.verticesi.data << "到顶点v(j):" << R_ALG.verticesj.data << "的路径" << endl;cout << "操作完毕！" << endl;system("pause");system("cls");continue;case '3': /返回上一界面break;default:system("cls"

17、;);cout << "输入错误，请重新输入！" << endl;continue;system("cls");break;break;case '4':return 0;default:system("cls");cout << "功能选择错误，请重新输入！" << endl;break;return 0;void main_menu(void)cout << endl;cout << "=" <&l

18、t; endl;cout << " 图 的 创 建 及 应 用 " << endl;cout << "<<=功 能 选 择=>>" << endl;cout << " 【1】邻接矩阵表示法 " << endl;cout << " 【2】邻接表表示法 " << endl;cout << " 【3】基于深度优先搜索判断是否存在指定位置的路径 " << end

19、l;cout << " 【4】退出程序 " << endl;cout << "=" << endl << endl;void minor_menu1(void)cout << "<<=邻接矩阵表示法=>>" << endl;cout << ">1.创建有向图" << endl;cout << ">2.显示图信息" << endl;

20、cout << ">3.返回上一界面" << endl;void minor_menu2(void)cout << "<<=邻接表表示法=>>" << endl;cout << ">1.创建有向图" << endl;cout << ">2.显示图信息" << endl;cout << ">3.返回上一界面" << endl;voi

21、d minor_menu3(void)cout << "<<=基于深度优先搜索判断是否存在指定路径=>>" << endl;cout << ">1.使用已创建的邻接表表示的图进行搜索判断" << endl;cout << ">2.创建新的图进行搜索判断" << endl;cout << ">3.返回上一界面" << endl;2.头文件”ADT.h”的部分程序如下：#ifndef

22、 ADT_H_#define ADT_H_/* 图 */* -图的数组（邻接矩阵）存储表示- */#define INFINITY INT_MAX /用整型最大值代替 #define MAX_VERTEX_NUM 20 /最大顶点数#define MAX_NAME 5 /顶点字符串的最大长度+1#define MAX_INFO 20 /相关信息字符串的最大长度+1#define MAXSIZE 100typedef enum MDG, MDN, UDG, UDN MGraphKind; /有向图，有向网，无向图，无向网typedef int VRType; /顶点关系类型，对无权图，用1或0t

23、ypedef char InfoType; /弧信息类型typedef char VertexTypeMAX_NAME; /顶点类型typedef struct ArcCellVRType adj; /表示相邻否；对带权图，则为权值类型InfoType *info; /弧相关信息的指针ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;/顶点向量AdjMatrix arcs; /邻接矩阵int vexnum, arcnum; /图的当前顶点数和弧数MGraphKin

24、d kind; /图种类标志MGraph;/* -图的邻接表存储表示- */typedef enum ADG, ADN, AUDG, AUDN ALGraphKind; / 有向图,有向网,无向图,无向网typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode * nextarc; /指向下一条弧的指针InfoType * info; /该弧相关信息指针ArcNode; /边表结点结构描述typedef struct VNodeVertexType data; /顶点信息ArcNode * firstarc; /指向第一条一幅该顶

25、点的弧的指针VNode, AdjListMAX_VERTEX_NUM; /顶点向量结点结构描述typedef structAdjList vertices; /邻接表 int vexnum,arcnum; /图的当前顶点数和弧数 ALGraphKind kind; /图的种类标志ALGraph; /邻接表结构描述int visitedMAX_VERTEX_NUM; /访问标志数组(全局量)Status(*VisitFunc)(VertexType); /函数变量#endif /* ADT_H_ */3.头文件"DataStructure_Graph.h"中部分函数定义如下：

26、#include <stdio.h>#include <malloc.h>#include "ADT.h"#include "DataStructure_StackQueue.h" /数据结构第三章栈和队列相关函数的定义及声明/* 功 能 函 数 声 明 区*/int LocateVex(MGraph G, VertexType u); /若G中存在顶点u,则返回该顶点在图中的位置，否则返回1Status CreateGraph(MGraph &G); /采用数组(邻接矩阵)表示法，构造图GStatus CreateDG(

27、MGraph &G); /采用数组（邻接矩阵）表示法，构造有向图GStatus CreateDN(MGraph &G); /采用数组（邻接矩阵）表示法，构造有向网GStatus CreateUDN(MGraph &G); /采用数组（邻接矩阵）表示法，构造无向图GStatus CreateUDG(MGraph &G); /采用数组（邻接矩阵）表示法，构造无向网GStatus DestroyGraph(MGraph &G); /销毁图GStatus DisplayGraph(MGraph G); /输出邻接矩阵表示图Gvoid DFSTraverse(MG

28、raph G, Status(*Visit)(int v); /深度优先搜索邻接矩形表示的图Gint LocateVex(ALGraph G, VertexType u); /若G中存在顶点u,则返回该顶点在图中的位置，否则返回1Status CreateGraph(ALGraph &G); /采用邻接表存储结构,构造没有相关信息的4种图GStatus DestroyGraph(ALGraph &G); /销毁图GVertexType* GetVex(ALGraph G, int v); /返回顶点v的值int FirstAdjVex(ALGraph G, VertexType

29、 v); /返回v的第一个邻接顶点的序号.若没有邻接顶点,返回-1Status DisplayGraph(ALGraph G); /输出邻接表表示图Gvoid DFSTraverse(ALGraph G, Status(*Visit)(int v);/深度优先搜索邻接表表示的图Gint exist_path_DFS(ALGraph G, int i, int j); /判断邻接表方式存储的有向图G是否存在顶点i到j路径/* 功 能 函 数 定 义 区*/*邻 接 矩 阵 表 示*/* 函数原型：int LocateVex(MGraph &G, VertexType u)* 函数功能：若

30、G中存在顶点u,则返回该顶点在图中的位置，否则返回1* 入口参数：已存在的图G,与G中顶点类型相同的顶点u* 出口参数：顶点在图中的位置，否则返回-1*/int LocateVex(MGraph G, VertexType u)int i = 0;for (int i = 0; i < G.vexnum; +i)if (strcmp(u, G.vexsi) = 0)return i;return -1; /LocateVex/* 函数原型：Status CreateGraph( MGraph &G ) * 函数功能：采用数组(邻接矩阵)表示法，构造图G* 入口参数：图G* 出口参

31、数：返回函数结果状态*/Status CreateGraph(MGraph &G)cout << "请输入图G的类型（有向图：0，有向网：1，无向图：2，无向网：3）："/cin >> kind; scanf_s("%d", &G.kind); / 自定义输入函数，读入一个随机值 switch (G.kind) case MDG: return CreateDG(G); / 构造有向图G case MDN: return CreateDN(G); / 构造有向网G case UDG: return CreateUD

32、G(G); / 构造无向图G case UDN: return CreateUDN(G); / 构造无向网G default : return ERROR; return OK; / CreateGraph/* 函数原型：Status CreateDG(MGraph &G)* 函数功能：采用数组（邻接矩阵）表示法，构造有向图G* 入口参数：图G* 出口参数：返回函数结果状态*/Status CreateDG(MGraph &G) int IncInfo;char sMAX_INFO, *info;VertexType va, vb; /顶点类型cout << &qu

33、ot;请输入有向图G的顶点数，弧数，弧是否含其他信息（是：1，否：0 以空格作为间隔)："cin >> G.vexnum >> G.arcnum >> IncInfo;cout << "请输入" << G.vexnum << "个顶点的值(少于" << MAX_NAME << "个字符）：" << endl;for (int i = 0; i < G.vexnum; +i) /构造顶点向量cin >>

34、 G.vexsi;for (int i = 0; i < G.vexnum; +i) /初始化邻接矩阵for (int j = 0; j < G.vexnum; +j)G.arcsij.adj = 0;G. = NULL;cout << "请输入" << G.arcnum << "条弧的弧尾 弧头(以空格作为间隔)：" << endl;for (int i = 0; i < G.arcnum; +i)cin >> va >> vb;int m

35、= LocateVex(G, va);if (m < 0)cout << "在图G中未找到" << va << endl;int n = LocateVex(G, vb);if (n < 0)cout << "在图G中未找到" << vb << endl;G.arcsmn.adj = 1; /有向图if (IncInfo)cout << "请输入该弧的相关信息(少于" << MAX_INFO << "个字符

36、）："cin >> s;int length = strlen(s);if (length)info = new charlength + 1;strcpy_s(info,length + 1,s);G. = info; /有向 G.kind = MDG;return OK; / CreateDG/* 函数原型：Status DisplayGraph(MGraph G)* 函数功能：输出邻接矩阵表示图G * 入口参数：图G* 出口参数：返回函数结果状态*/Status DisplayGraph(MGraph G)const int MAX_STR_G

37、 = 8;const int MAX_STR_ARC = 5;char sMAX_STR_G, s1MAX_STR_ARC;switch (G.kind)case MDG: strcpy_s(s, MAX_STR_G, "有向图0");strcpy_s(s1, MAX_STR_ARC, "弧0");break;case MDN: strcpy_s(s, MAX_STR_G, "有向网0");strcpy_s(s1, MAX_STR_ARC, "弧0");break;case UDG: strcpy_s(s, MAX

38、_STR_G, "无向图0");strcpy_s(s1, MAX_STR_ARC, "边0");break;case UDN: strcpy_s(s, MAX_STR_G, "无向网0");strcpy_s(s1, MAX_STR_ARC, "边0");printf(" %sG的信息：%d个顶点 %d条%sn", s,G.vexnum, G.arcnum, s1);for (int i = 0; i < G.vexnum; +i) /输出G.vexsprintf("G.vexs%

39、d=%sn", i, G.vexsi);printf("G.arcs.adj:n"); / 输出G.arcs.adjfor (int i = 0; i < G.vexnum; i+)for (int j = 0; j < G.vexnum; j+)printf("%6d", G.arcsij.adj);printf("n");printf("G.:n"); /输出G.printf("顶点1(弧尾) 顶点2(弧头) 该%s信息：n", s1

40、);if (G.kind < 2) /有向for (int i = 0; i < G.vexnum; i+)for (int j = 0; j < G.vexnum; j+)if (G.arcsij.adj)printf("%5s ->%5s ", G.vexsi, G.vexsj);if (G.)printf("%7sn", G.);elseprintf(" nulln"); else /无向for (int i = 0; i<G.vexnum; i+)for

41、 (int j = i + 1; j < G.vexnum; j+)if (G.arcsij.adj)printf("%5s ->%5s ", G.vexsi, G.vexsj);if (G.)printf("%7sn", G.);elseprintf(" nulln");return OK; /DisplayGraph/*图的邻接表存储*/* 函数原型：int LocateVex(ALGraph G, VertexType u)* 函数功能：若G中存在顶点u,则返回该顶点在图中

42、的位置，否则返回1* 入口参数：已存在的图G,与G中顶点类型相同的顶点u* 出口参数：顶点在图中的位置，否则返回-1*/int LocateVex(ALGraph G, VertexType u)int i;for (i = 0; i<G.vexnum; +i)if (strcmp(u, G.verticesi.data) = 0)return i;return -1; /LocateVex/* 函数原型：CreateGraph(ALGraph &G)* 函数功能：采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)* 入口参数：图G* 出口参数：返回函数结果状态*

43、/Status CreateGraph(ALGraph &G)int w; /权值VertexType va, vb;ArcNode *p;printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");scanf_s("%d", &G.kind);printf("请输入图的顶点数 边数(以空格分隔): ");cin >> G.vexnum >> G.arcnum;printf("请输入%d个顶点的值(少于%d个字符):n", G.vexnum, M

44、AX_NAME);for (int i = 0; i<G.vexnum; +i) /构造顶点向量cin >> G.verticesi.data;G.verticesi.firstarc = NULL;if (G.kind = 1 | G.kind = 3) /网 printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):n");else /图printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n");for (int k = 0; k<G.arcnum; +k) /构造表结点链表if (G.kind = 1 | G.kind = 3) /网 cin >> w >> va >> vb;else /图cin >> va >> vb;in