7图的遍历上机实验要求.docVIP

大 连 海 事 大 学Dalian 大 连 海 事 大 学 Dalian Maritime University 《数据结构》实 验 报 告 Training Item 学生姓名 王贤 专业年级 信息管理与信息系统 班 成绩 评语 教师签字： 实验题目 图的遍历 实验目的 1．掌握理解图的两种主要存储结构（邻接矩阵和邻接表）； 2．掌握图的构造； 3. 掌握图深度优先遍历、广度优先遍历算法。 实验原理 深度优先有哪些信誉好的足球投注网站遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先有哪些信誉好的足球投注网站可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 实验内容与要求 问题描述： 图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 根据从键盘输入的数据创建图（图的存储结构可采用邻接表），并对图进行深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站 要求： 设计要求 图的存储可采用邻接表或邻接矩阵； 定义下列过程：???? CreateGraph():?按从键盘的数据建立图???? DFSGrahp()：深度优先遍历图? BFSGrahp()：广度优先遍历图? Print()：显示顶点 int?FirstAdjVex(Graph?G,int?v){?? if(G.vertex[v].firstarc)??? return?G.vertex[v].firstarc-adjvex;?? else???? return?-1;? }?? int?NextAdjVex(Graph?G,int?v,int?w){?? ArcNode*?p?=?G.vertex[v].firstarc;?? while(p-adjvex!=w)??? p?=?p-nextarc;?? if(p-nextarc)??? return?p-nextarc-adjvex;?? else???? return?-1;? }?? 首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。 主控菜单设计要求：程序运行后，在主程序中提供下列菜单：????????????? 1…图的建立???????? 2…深度优先遍历图???????? 3…广度优先遍历图?? 4…结束 请选择菜单1—4： 功能要求 1．从终端输入图的信息。 2．完成各菜单的功能，并能正确显示图的遍历序列 实现要求 用VC++环境 图的信息在主函数中输入。 实验报告要求 不要求书面实验报告 电子版实验报告要求如下 画出遍历的图 (可不做) 输入数据截屏 附加输出结果 实现程序的代码 说明程序设计过程中的难点、解决办法及编程小结或体会。（可不做） 实验程序待抽查 （电子） 备注： 源代码： #includestdio.h #includemalloc.h #define max 100 //最大顶点个数 typedef struct //以下定义临接矩阵类型 { int number; //顶点编号 int info; //顶点其他信息,边的权值 }VertexType; //顶点类型 typedef struct //图的定义 { int edges[max][max]; //邻接矩阵 int n,e; //顶点数和弧数 VertexType vexs[max]; //存放定点信息 }MGraph; //图的邻接矩阵类型 //定义邻接表类型 typedef struct ANode //弧的结点结构类型 { int adjvex; //弧的重点位置,就是放值的 struct ANode *nexta