2016010571-贾明华-实验四

《2016010571-贾明华-实验四》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验报告课程名称数据结构实验项目实验四-创建一个图并输出图的深度优先和广度优先遍历结果班级/学号学生姓名实验日期计算机学院计算机大类计类16112016010571贾明华（2017年12月5日）实验题目：实验四……创建一个图并输出图的深度优先和广度优先遍历结果一、实验目的1）掌握图的存储结构；2）掌握并实现图的深度优先和广度优先遍历算法；3）理解图的应用，包括最小生成树、拓扑排序、关键路径、最短路径；二、实验内容1）以邻接矩阵或邻接表创建一个图，要求能够动态输入；2）输岀深度优先和广度优先遍历序列；3）三选一应用题：1）两种算法构造最小生成树；2）

2、有向无环图的拓扑排序和关键路径计算；3）两种算法计算最短路径。三、设计与编码1）实验题目及主要存储结构【验证型题目1］创建一个图并输出图的深度优先和广度优先遍历结果（要求以邻接矩阵或邻接表形式创建一个图，输出图的两种遍历结果。）采用邻接表储存结构，将图的顶点、边的信息分别存在邻接表的data域和指针域。（提示：请根据所选定题目，描述主要存储结构定义，语言不限）2）结合题目，说明利用栈或队列解决问题的基本算法描述〈1＞图的创建采用邻接表储存结构，创建图。voidCrerateGraph（Graph*G）//创建图ArcNode*p;printfC11

3、请输入图的顶点数和边数:”)；scanf(n%d%dH,&G->v,&G・>a);getchar();printf(n请输入％d个顶点的信息:”,G・>v);for(i=0;iv;i++){scanf("%s"，&G->adjlist[i].data);//读入顶点信息G->adjlist[i].firstarc=NULL;//边表置为空表for(i=0;ia;i++){printfT输入第％(1条边(起点序号，终点序号)i+1);scanf(u%d%dH,&m,&n);//输入无序对，顶点编号0开始p=(ArcNode*)mall

4、oc(sizeof(ArcNode));p->adjvex=n;p->nextarc=G->adjlist[m].firstarc;G->adjlist[m].firstarc=p;p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=m;p->nextarc=G->adjlist[n].firstarc;G->adjlist[n].firstarc=p;}}〈2〉图的深度优先遍历首先初始化标志数组，然后默认以vi(1=0)为开始的顶点，递归调用程序屮的DFSGraph子函数，子函数中继续递归调用自己(DFSG

5、raph函数)，直到所有顶点都被访问。voidDFSGraph(GraphG,inti)//深度优先遍历{ArcNode*p;printf(”访问顶点:％c”,G.adjlist[i].data);〃访问顶点ivisited[i]=l;p=G.adjlist[i].firstarc;while(p)〃从p的邻接点出发进行深度优先搜索{if(!visited[p->adjvex])DFSGraph(G,p->adjvex);p=p->nextarc;〃找指向下一条弧的指针}}voidDFSTraverse(GraphG){inti;for(i=0

6、;i图的广度优先遍历广度优先遍历采用的是队列，因此在开始的地方创建了关于队列的子函数，为了BFSGraph函数的正确使用，又为其创建了InitQucuc(构造一个空的对列)、Enqueue(入队列)、DEQueue(出队列)这三个队列子函数。然后根据队列先进先出、后进后出的原则，同样，默认是从vi(i=O)为开始的顶点，让图的顶点进入队列然后出队。voidBF

7、SGraph(GraphG)〃广度优先遍历{inti,k;Queueq;ArcNode*p;for(i=0;iadjvex

8、]){printf(H访问顶点：％cM,G.adjlist[p->adjvex].data);visitedfp->a