图的邻接表存储实现和深度优先遍历.docVIP

第四次实验报告 图的邻接表存储实现及深度优先遍历 学号0708140119 电子072 姓名 陆萍萍 问题描述 程序所能达到的基本功能 构建以邻接表形式存储的表及实现深度优先遍历并输出结果。 2、 输入的形式和输入值的范围： 根据提示进行输入：先输入要构建的表的结点数和边数，要求是整型； 输入各结点的代号，这里用char型，也可在源程序中改变其它形式； 输入各边的头结点和尾结点的代号； 输出的形式 若正常输入，则输出深度优先遍历的最后结果。用各结点的代码表示。 测试数据要求 第一组数据： 结点数和边数：4 4 结点名称：a b c d 边：a-b a-c b-c c-d 输出a-b-c-d-over! 第二组数据： 图如下： 输出 a-b-c-d-e-f-g-over! 概要设计 抽象数据类型，它们的作用 //图的结点类 templateclass T class TVex {}; //图类 templateclass T class Graph {}//链表存储 2主程序流程及模块调用关系 主程序模块： void main { 构造一个图，对T实例化（char）。 调用Graph中的Create函数； 调用Graph中的DFS函数； } （2）调用关系如下 核心算法的粗线条伪码 详细设计（要求主要变量和语句加注释） 抽象数据类型的实现：包括类型定义和各个操作的实现。 1) TVex的详细设计 （1）私有数据类型的定义 private： T m_elem; TLinklistint m_arcs; 2)Graph的详细设计 （1）私有数据类型的定义 private： TVexT Vextex[maxnum]; int vexnum; int arcnum; int kind; int symbol[maxnum]; （2）公有函数成员的定义 Graph()； void Create(); int LocateVex(T v); void DFS(); void DFS_IN(int i); (3)具体实现 ★templateclass T void GraphT::Create() { T v1,v2; int i,j; cout*********************基本信息*****************************endl; cout请分别输入结点数和边数: ; cinvexnumarcnum; cout***********************结点***************************endl; for(int l=0;lvexnum;l++) { cout请输入第l+1个结点的代号 ; cinVextex[l].m_elem; } cout***********************边数***************************endl; for(int k=0;karcnum;k++) { cout请输入第k+1边的头结点和尾结点 ; cinv1v2; i=LocateVex(v1); j=LocateVex(v2); Vextex[i].m_arcs.InsertLate(j); Vextex[j].m_arcs.InsertLate(i); } cout************************结果**************************endl; } ★templateclass T int GraphT::LocateVex(T v) { for(int i=0;ivexnumVextex[i].m_elem!=v;i++); if(i==vexnum) return -1; else return i; } ★templateclass T void GraphT::DFS() { DFS_IN(0); coutover!endl; } ★templateclass T void GraphT::DFS_IN(int i) { int index; symbol[i]=1; coutVextex[i].m_elem--; for(int j=0;;j++)