图的基本操作与kruskal最小生成树实验报告

《图的基本操作与kruskal最小生成树实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构22实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容[问题描述]　　对给定图，实现图的深度优先遍历和广度优先遍历。[基本要求]　　　以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。【测试数据】　　由学生依据软件工程的测试技术自己确定。三、实验前的准备工作1、掌握图的相关概念。2、掌握图的逻辑结构和存储结构。3、掌握图的两种遍历算法的实现。四、详细设计22建立结构体创建图END调用greatUDN函数调用BFS

2、Traverse函数输入起始节点名称深度优先遍历输出广度优先遍历输出调用DFSTraverse函数五、源程序#defineINFINITY10000#defineMAX_VERTEX_NUM40#defineMAX40#include#include#include#includetypedefstructArCell{intadj;}ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charname[20];}infotyp

3、e;22typedefstruct{infotypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;}MGraph;intLocateVex(MGraph*G,char*v){intc=-1,i;for(i=0;ivexnum;i++)if(strcmp(v,G->vexs[i].name)==0){c=i;break;}returnc;}MGraph*CreatUDN(MGraph*G)//初始化图，接受用户输入{inti,j,k,w;charv1[20],v2[20];printf("请输入图的顶点数,弧数:

4、");scanf("%d%d",&G->vexnum,&G->arcnum);printf("结点名字:");for(i=0;ivexnum;i++){printf("No.%d:",i+1);scanf("%s",G->vexs[i].name);}for(i=0;ivexnum;i++)for(j=0;jvexnum;j++)G->arcs[i][j].adj=INFINITY;printf("请输入一条边依附的两个顶点和权值:");for(k=0;karcnum;k++){printf("第%d条边:",k+1);printf

5、("起始结点:");scanf("%s",v1);printf("结束结点:");scanf("%s",v2);printf("边的权值:");scanf("%d",&w);i=LocateVex(G,v1);j=LocateVex(G,v2);if(i>=0&&j>=0){G->arcs[i][j].adj=w;G->arcs[j][i]=G->arcs[i][j];}}returnG;22}intFirstAdjVex(MGraph*G,intv){inti;if(v<=0&&vvexnum){//v合理for(i=0;ivexnum;i++)if(G->

6、arcs[v][i].adj!=INFINITY)returni;}return-1;}voidVisitFunc(MGraph*G,intv){printf("%s",G->vexs[v].name);}intNextAdjVex(MGraph*G,intv,intw){intk;if(v>=0&&vvexnum&&w>=0&&wvexnum)//v,w合理{for(k=w+1;kvexnum;k++)if(G->arcs[v][k].adj!=INFINITY)returnk;}return-1;}intvisited[MAX];voidDFS(M

7、Graph*G,intv)//从第v个顶点出发递归地深度优先遍历图G{intw;visited[v]=1;VisitFunc(G,v);//访问第v个结点for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w]){DFS(G,w);printf("%d",G->arcs[v][w].adj);}}voidDFSTraverse(MGraph*G,char*s)//深度优先遍历{intv,k;for(v=0;vvexnum;v++