《大数据结构与算法实验图地基本操作》由会员分享，可在线阅读，更多相关《大数据结构与算法实验图地基本操作（9页珍藏版）》请在金锄头文库上搜索。
1、word图的根本操作实验报告图的根本操作实验报告实验名称图的根本操作实验目的1. 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表的存储结构；2. 遍历是图各种应用的算法的根底，要熟练掌握图的深度优先遍历和广度优先遍历的算法，复习栈和队列的应用；3. 掌握以邻接矩阵作为存储结构的生成图的最小生成树的普利姆算法；实验内容编制一个演示图的邻接表的创建、深度遍历、广度遍历操作的程序。问题描述用数据结构相关知识，实现邻接表的定义和操作。该程序包括图的邻接表的结点类型定义以与对图操作的具体的函数定义包括：建立图的邻接表、深度优先遍历图、广度优先遍历图。问题分析该实验是基于C语言和数据结构知识根底的对
2、图的根本操作的检验，无需设计复杂的算法，程序语句也相对简单。因此，我直接按要求定义了对图操作的具体函数，并于主函数中实现对应的功能调用。 实验步骤1需求分析本演示程序用VC+编写，完成图的邻接表的生成、遍历根本操作。 输入的形式和输入值的X围：在输入邻接表顶点信息前，必须先确定该信息能正确创建邻接表。 输出的形式：在所有三种操作中都显示操作是否正确以与操作后图的内容。 程序所能达到的功能：完成图的邻接表的生成、深度优先遍历、广度优先遍历根本操作。 测试数据：创建操作中依次输入7,7作为顶点数和边数，以0,10,21,31,53,43,64,5作为各顶点信息生成一个邻接表。2概要设计1为了实现上
3、述程序功能，需要定义二叉树的抽象数据类型：ADTGraph数据对象：顶点的有穷非空集合和边的集合数据关系：结点具有一样的数据类型与层次结构根本操作：Void InitGraph(ALGraph *G) 初始条件：无操作结果：初始化图Void DFSTraverse(ALGraph *G)初始条件：图Graph已存在操作结果：按深度优先遍历图的邻接表Void BFSTraverse(ALGraph *G)初始条件：图Graph已存在操作结果：按广度优先遍历图的邻接表2本程序包含7个函数：主函数main()建立一个图的邻接表函数CreateGraphAL ()深度优先遍历图 DFS()广度优先遍历
4、 BFS()函数说明#include #include #define MaxVertexNum 100#define QueueSize 30 typedef enumFALSE,TRUEBoolean; Boolean visitedMaxVertexNum; typedef char VertexType;typedef int EdgeType;typedef struct node/边表结点int adjvex;/邻接点域struct node *next;/域链/假如是要表示边上的权,如此应增加一个数据域EdgeNode;typedef struct vnode/顶点边结点Vert
5、exType vertex;/顶点域EdgeNode *firstedge;/边表头指针VertexNode;typedef VertexNode AdjListMaxVertexNum;/AdjList是邻接表类型typedef struct AdjList adjlist;/邻接表int n,e;/图中当前顶点数和边数ALGraph;void CreateGraphAL (ALGraph *G) int i,j,k; EdgeNode * s; printf(请输入顶点数和边数(输入格式为:顶点数,边数)：n); scanf(%d,%d,&(G-n),&(G-e); / 读入顶点数和边数
6、printf(请输入顶点信息(输入格式为:顶点号)每个顶点以回车作为完毕:n); for (i=0;in;i+) / 立有n个顶点的顶点表 scanf(n%c,&(G-adjlisti.vertex); / 读入顶点信息 G-adjlisti.firstedge=NULL; / 点的边表头指针设为空 printf(请输入边的信息(输入格式为:i,j)：n); for (k=0;ke;k+) / 建立边表 scanf(n%d,%d,&i,&j); / 读入边的顶点对应序号 s=new EdgeNode; / 生成新边表结点s s-adjvex=j; / 邻接点序号为j s-next=G-adjl
7、isti.firstedge; / 将新边表结点s插入到顶点Vi的边表头部 G-adjlisti.firstedge=s; s=new EdgeNode;s-adjvex=i;s-next=G-adjlistj.firstedge;G-adjlistj.firstedge=s; /*/* 深度优先遍历 */*/ void DFS(ALGraph *G,int i) /以vi为出发点对邻接表表示的图G进展深度优先搜索 EdgeNode *p;printf(visit vertex:%cn,G-adjlisti.vertex); / 访问顶点vivisitedi=TRUE;/标记vi已访问p=G-
8、adjlisti.firstedge; /取vi边表的头指针while(p)/依次搜索vi的邻接点vj，这里j=p-adjvexif (!visitedp-adjvex)/假如vi尚未被访问DFS(G,p-adjvex);/如此以Vj为出发点向纵深搜索p=p-next; /找vi的下一邻接点void DFSTraverseM(ALGraph *G) int i; for(i=0;in;i+) visitedi=FALSE; for(i=0;in;i+) if(!visitedi) DFS(G,i); /*/* 广度优先遍历 */*/typedef struct int front; int r
9、ear; int count; int dataQueueSize; CirQueue; void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0; int QueueEmpty(CirQueue *Q) return Q-front=Q-rear; int QueueFull(CirQueue *Q) return (Q-rear+1)%QueueSize=Q-front; void EnQueue(CirQueue *Q,int x) if (QueueFull(Q) printf(Queue overflow); else Q-cou
10、nt+; Q-dataQ-rear=x; Q-rear=(Q-rear+1)%QueueSize; int DeQueue(CirQueue *Q) int temp; if(QueueEmpty(Q) printf(Queue underflow); return false; else temp=Q-dataQ-front; Q-count-; Q-front=(Q-front+1)%QueueSize; return temp; void BFS(ALGraph*G,int k)/ 以vk为源点对用邻接表表示的图G进展广度优先搜索 int i;CirQueue Q;/须将队列定义中Dat
11、aType改为intEdgeNode *p;InitQueue(&Q);/队列初始化printf(visit vertex:%cn,G-adjlistk.vertex);/访问源点vkvisitedk=TRUE; EnQueue(&Q,k);/vk已访问，将其人队。实际上是将其序号人队while(!QueueEmpty(&Q)/队非空如此执行i=DeQueue(&Q);/相当于vi出队p=G-adjlisti.firstedge;/取vi的边表头指针while(p)/依次搜索vi的邻接点vj(令p-adjvex=j)if(!visitedp-adjvex)/假如vj未访问过printf(visit vertex:%cn,G-ad
