资源描述：
《数据结构与算法实验图的基本操作》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、1的基本操作实验报告图的基本操作实验报告实验名称图的基本操作实验目的1.掌握阁的各种存储结构，特别耍熟练掌握邻接矩阵和邻接表的存储结构；2.遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历的算法，复习栈和队列的应用；1.掌握以邻接矩阵作为存储结构的生成图的最小生成树的普利姆算法；实验内容编制一个演示图的邻接表的创建、深度遍历、广度遍历操作的程序。问题描述用数据结构和关知识，实现邻接表的定义和操作。该程序包括图的邻接表的结点类型定义以及对图操作的具体的函数定义(包括：建立图的邻接表、深度优先遍历图、广
2、度优先遍历图)。问题分析该实验是基于C语言和数据结构知识基础的对图的基木操作的检验，无需设计复杂的算法，程序语句也相对简单。因此，我直接按要求定义了对图操作的具体函数，并于主函数屮实现对应的功能调用。实验步骤1.需求分析本演示程序用VC++编写，完成图的邻接表的生成、遍历棊本操作。①输入的形式和输入值的范围：在输入邻接表顶点信息前，必须先确定该信息能正确创建邻接表。②输岀的形式：在所有三种操作中都显示操作是否正确以及操作后图的内容。③程序所能达到的功能：完成图的邻接表的生成、深度优先遍历、广度优先遍历基本操作。④测试数据
3、：创建操作中依次输入7,7作为顶点数和边数，以(0,1)(0,2)(1,3)(1,5)(3,4)(3,6)(4,5)作为各顶点信息生成一个邻接表。2.概要设计1)为了实现上述程序功能，需耍定义二叉树的抽象数据类型：ADTGraph{数据对象：顶点的有穷非空集合和边的集合数据关系：结点具冇相同的数据类型及层次结构基本操作：VoidlnitGraph(ALGraph*G)初始条件：无操作结果：初始化图VoidDFSTraverse(ALGraph*G)初始条件：图Graph己存在操作结果：按深度优先遍历阁的邻接表VoidBF
4、STraverse(ALGraph*G)初始条件：图Graph已存在操作结果：按广度优先遍历图的邻接表2)本程序包含7个函数：①主函数main()②建立一个阁的邻接表函数CreateGraphAL()③深度优先遍历阁DFS(＞④广度优先遍历BFS()函数说明#includeinclude//defineMaxVertexNum100#defineQueueSize30typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum]
5、;typedefcharVertexType;typedefintEdgeType;typedefstructnode//边表结点{intadjvex;//邻接点域structnode*next;//域链//若是要表示边上的权，则应增加一个数据域JEdgeNode;typedefstructvnode//顶点边结点{VertexTypevertex;//顶点域EdgeNode*firstedge;//边表头指针JVertexNode;typedefVertexNodeAdjList[MaxVertexNum];//Adj
6、List是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图巾当前顶点数和边数}ALGraph;voidCreateGraphAL(ALGraph*G){inti,j,k;EdgeNode*s;printf("请输入顶点数和边数(输入格式为:顶点数，边数-);scanf("%d,%d",&(G->n),&(G->e>);//读入顶点数和边数printf("请输入顶点信息(输入格式为:顶点号4叫每个顶点以回车作为结束for(i=O;in;i++)//立有n个顶点的
7、顶点表{scanf("%c"/&(G->adjlist[i].vertex));//读入顶点信息G->adjlist[i].firstedge=NULL;//点的边表头指针设为空}printf("请输入边的信息(输入格式为:i,j):");for(k=0;ke;k++)//建立边表{scanf("%d，％d",&i，&j};//读入边<^>的顶点对应序号s=newEdgeNode;//生成新边表结点ss->adjvex=j;//邻接点序号为js->next=G->adjlist[i].firstedg
8、e;//将新边表结点s插入到顶点Vi的边表头部G->adjlist[i].firstedge=s;s=newEdgeNode;s->adjvex=i;s->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s;}}y木氺本氺木木氺木木木氺木氺木氺木木氺木木木氺木
