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

姓名学号实验项目图的创建及应用（I）实验内容1编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接矩阵和邻接表存储结构并输出显示。（题集150页5.3扩充）存储结构定义分别参见教材第161页和第163页。2试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（ij）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。（题集第49页7.27）算法设计与程序实现：算法分析 本次实验主函数采用循环选择结构，主函数调用自己编写的头文件DataStructure_Graph.h中的相关功能函数，完成实验要求。 主程序结构：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、返回上一界面；4、退出程序 创建图的算法分析 邻接矩阵结构创建图：首先由键盘输入待创建的图的顶点数，弧数以及是否含有弧信息，然后由顶点数控制循环构造顶点向量,接着由顶点数控制循环初始化邻接矩阵(adj=0,info=NUll)，再次输入弧信息，此时将输入的弧的弧头和弧尾与顶点信息进行匹配，从而确定弧在邻接矩阵中的位置(有弧时为1)，如果输入的弧有信息的话，在进行有无弧的判断写邻接矩阵时进行绑定，有键盘输入即可。 邻接表结构创建图：首先由键盘输入待创建的图的顶点数，弧数，然后由顶点数控制循环初始化顶点信息(顶点数据信息及顶点第一条弧指针(firstarc = NULL),接着由弧数控制循环输入弧头和弧尾顶点，与之前建立的顶点信息进行匹配，从而确定弧头和弧尾的位置信息，此时生成一个弧结点类型的存储空间，采用单链表中在表头插入新结点的方法，将弧的信息插入到顶点的第一条弧之后，如同此法，对每个顶点都进行以上操作，这就建立了图的邻接表结构。深度优先搜索判断是否存在指定位置的路径算法分析首先判断指定的两个位置向量是否相等，如果相等，则肯定有路径相连，否则从指定的弧头结点开始搜索，将该顶点访问过的弧的访问标志置1，任何到该弧的弧头顶点进行如上操作，当搜索该顶点的所有弧都没有找到则返回0，然后返回上一顶点，对该顶点的其他弧进行访问。当指定顶点的所有弧都被搜索访问过都没有找到，此时程序返回0。核心程序此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释处，核心程序如下：1.主函数如下：#include iostream /输入输出流库头文件#include fstream /文件操作流库头文件#include windows.h /cmd窗口设置函数头文件#include ADT.h /数据结构中相关结构体类型定义及相关数据类型定义#include DataStructure_Graph.h /数据结构第七章图相关函数的定义及声明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(); /主菜单显示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 ch1;switch (ch1)case 1: /创建有向图system(cls);CreateGraph(MG);cout 操作完毕！ endl;system(pause);system(cls);continue;case 2: /显示图信息system(cls);DisplayGraph(MG);cout 操作完毕！ endl;system(pause);system(cls);continue;case 3: /返回上一界面break;default:system(cls);cout 输入错误，请重新输入！ endl;continue;system(cls);break;break;case2:system(cls);while (1)minor_menu2();char ch1;/二层菜单输入选择 cout endl 请选择功能：;cin ch1;switch (ch1)case 1:/创建图信息system(cls);CreateGraph(ALG);cout 操作完毕！ endl;system(pause);system(cls);continue;case 2:/显示图信息system(cls);DisplayGraph(ALG);cout 操作完毕！ endl;system(pause);system(cls);continue;case3: /返回上一界面break;default:system(cls);cout 输入错误，请重新输入！ endl;continue;system(cls);break;break;case 3:system(cls);while (1)minor_menu3();ALGraph R_ALG;int i, j; /待搜索的顶点的位置char ch1; /二层菜单输入选择 cout endl 请选择功能：;cin ch1;switch (ch1)case 1:/使用已创建的邻接表表示的图进行搜索system(cls);cout 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 到顶点v(j): G.verticesj.data 的路径 endl;cout 操作完毕！ endl;system(pause);system(cls);continue;case 2: /创建新图进行搜索system(cls);CreateGraph(R_ALG);cout 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): R_ALG.verticesi.data 到顶点v(j): R_ALG.verticesj.data 的路径 endl;cout 操作完毕！ endl;system(pause);system(cls);continue;case 3: /返回上一界面break;default:system(cls);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 = endl;cout 图 的 创 建 及 应 用 endl;cout endl;cout 【1】邻接矩阵表示法 endl;cout 【2】邻接表表示法 endl;cout 【3】基于深度优先搜索判断是否存在指定位置的路径 endl;cout 【4】退出程序 endl;cout = endl endl;void minor_menu1(void)cout endl;cout 1.创建有向图 endl;cout 2.显示图信息 endl;cout 3.返回上一界面 endl;void minor_menu2(void)cout endl;cout 1.创建有向图 endl;cout 2.显示图信息 endl;cout 3.返回上一界面 endl;void minor_menu3(void)cout endl;cout 1.使用已创建的邻接表表示的图进行搜索判断 endl;cout 2.创建新的图进行搜索判断 endl;cout 3.返回上一界面 endl;2.头文件”ADT.h”的部分程序如下：#ifndef 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或0typedef 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; /图的当前顶点数和弧数MGraphKind 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; /指向第一条一幅该顶点的弧的指针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中部分函数定义如下：#include #include #include ADT.h#include DataStructure_StackQueue.h /数据结构第三章栈和队列相关函数的定义及声明/* 功 能 函 数 声 明 区*/int LocateVex(MGraph G, VertexType u); /若G中存在顶点u,则返回该顶点在图中的位置，否则返回1Status CreateGraph(MGraph &G); /采用数组(邻接矩阵)表示法，构造图GStatus CreateDG(MGraph &G); /采用数组（邻接矩阵）表示法，构造有向图GStatus CreateDN(MGraph &G); /采用数组（邻接矩阵）表示法，构造有向网GStatus CreateUDN(MGraph &G); /采用数组（邻接矩阵）表示法，构造无向图GStatus CreateUDG(MGraph &G); /采用数组（邻接矩阵）表示法，构造无向网GStatus DestroyGraph(MGraph &G); /销毁图GStatus DisplayGraph(MGraph G); /输出邻接矩阵表示图Gvoid DFSTraverse(MGraph 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 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)* 函数功能：若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* 出口参数：返回函数结果状态*/Status CreateGraph(MGraph &G)cout kind; scanf_s(%d, &G.kind); / 自定义输入函数，读入一个随机值 switch (G.kind) case MDG: return CreateDG(G); / 构造有向图G case MDN: return CreateDN(G); / 构造有向网G case UDG: return CreateUDG(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 G.vexnum G.arcnum IncInfo;cout 请输入 G.vexnum 个顶点的值(少于 MAX_NAME 个字符）： endl;for (int i = 0; i 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 va vb;int m = 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 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 = 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_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%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);if (G.kind 2) /有向for (int i = 0; i G.vexnum; i+)for (int j = 0; j %5s , G.vexsi, G.vexsj);if (G.)printf(%7sn, G.);elseprintf( nulln); else /无向for (int i = 0; iG.vexnum; i+)for (int j = i + 1; j %5s , G.vexsi, G.vexsj);if (G.)printf(%7sn, G.);elseprintf( nulln);return OK; /DisplayGraph/*图的邻接表存储*/* 函数原型：int LocateVex(ALGraph G, VertexType u)* 函数功能：若G中存在顶点u,则返回该顶点在图中的位置，否则返回1* 入口参数：已存在的图G,与G中顶点类型相同的顶点u* 出口参数：顶点在图中的位置，否则返回-1*/int LocateVex(ALGraph G, VertexType u)int i;for (i = 0; i G.vexnum G.arcnum;printf(请输入%d个顶点的值(少于%d个字符):n, G.vexnum, MAX_NAME);for (int i = 0; i G.verticesi.data;G.verticesi.firstarc = NULL;if (G.kind = 1 | G.kind = 3) /网 printf(请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):n);else /图printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n);for (int k = 0; k w va vb;else /图cin va vb;int m = LocateVex(G, va); /弧尾int n = LocateVex(G, vb); /弧头p = (ArcNode*)malloc(sizeof(ArcNode);p-adjvex = n;if (G.kind = 1 | G.kind = 3) /网p-info = (char *)malloc(sizeof(char);*(p-info) = w;elsep-info = NULL; /图p-nextarc = G.verticesm.firstarc; /插在表头G.verticesm.firstarc = p;if (G.kind = 2) /无向图或网,产生第二个表结点p = (ArcNode*)malloc(sizeof(ArcNode);p-a