大数据结构与算法实验——图地基本操作

1、实用标准文案图的基本操作实验报告精彩文档实用标准文案图的基本操作实验报告实验名称图的基本操作实验目的1. 掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表的存储结构；2. 遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历的算法，复习栈和队列的应用；3. 掌握以邻接矩阵作为存储结构的生成图的最小生成树的普利姆算法；实验内容编制一个演示图的邻接表的创建、深度遍历、广度遍历操作的程序。问题描述用数据结构相关知识， 实现邻接表的定义和操作。 该程序包括图的邻接表的结点类型定义以及对图操作的具体的函数定义 （包括：建立图的邻接表、 深度优先遍历图、广度优先遍历图） 。问题分析该

2、实验是基于 C 语言和数据结构知识基础的对图的基本操作的检验， 无需设计复杂的算法，程序语句也相对简单。 因此，我直接按要求定义了对图操作的具体函数，并于主函数中实现对应的功能调用。实验步骤1需求分析本演示程序用 VC+编写，完成图的邻接表的生成、遍历基本操作。输入的形式和输入值的范围：在输入邻接表顶点信息前，必须先确定该信息能正确创建邻接表。输出的形式：在所有三种操作中都显示操作是否正确以及操作后图的内容。程序所能达到的功能：完成图的邻接表的生成、深度优先遍历、广度优先遍历基本操作。 测试数据：创建操作中依次输入 7,7 作为顶点数和边数，以（ 0,1 ）（0,2 ）（ 1,3 ）（ 1,5

3、 ）（ 3,4 ）（3,6 ）（4,5 ）作为各顶点信息生成一个邻接表。精彩文档实用标准文案2概要设计1）为了实现上述程序功能，需要定义二叉树的抽象数据类型：ADT Graph数据对象：顶点的有穷非空集合和边的集合数据关系：结点具有相同的数据类型及层次结构基本操作：Void InitGraph(ALGraph *G)初始条件：无操作结果：初始化图Void DFSTraverse( ALGraph *G )初始条件：图 Graph 已存在操作结果：按深度优先遍历图的邻接表Void BFSTraverse( ALGraph *G )初始条件：图 Graph 已存在操作结果：按广度优先遍历图的邻接表

4、2）本程序包含 7 个函数：主函数 main() 建立一个图的邻接表函数 CreateGraphAL () 深度优先遍历图 DFS () 广度优先遍历 BFS()函数说明#include <stdio.h>#include <stdlib.h>#define MaxVertexNum 100#define QueueSize 30typedef enumFALSE,TRUEBoolean;Boolean visitedMaxVertexNum;typedef char VertexType;typedef int EdgeType;typedef struct node

5、/ 边表结点int adjvex;/ 邻接点域struct node *next;/ 域链/ 若是要表示边上的权 , 则应增加一个数据域EdgeNode;typedef struct vnode/ 顶点边结点VertexType vertex;/ 顶点域EdgeNode *firstedge;/边表头指针VertexNode;typedef VertexNode AdjListMaxVertexNum;/AdjList是邻接表类型typedef structAdjList adjlist;/ 邻接表精彩文档实用标准文案int n,e;/ 图中当前顶点数和边数ALGraph;void Creat

6、eGraphAL (ALGraph *G)int i,j,k;EdgeNode * s;printf("请输入顶点数和边数( 输入格式为 : 顶点数 , 边数 ) ： n");scanf("%d,%d",&(G->n),&(G->e);/读入顶点数和边数printf("请输入顶点信息( 输入格式为 : 顶点号 <CR>)每个顶点以回车作为结束:n");for (i=0;i<G->n;i+)/立有 n 个顶点的顶点表scanf("n%c",&(G->a

7、djlisti.vertex); /读入顶点信息G->adjlisti.firstedge=NULL;/点的边表头指针设为空printf("请输入边的信息( 输入格式为 :i,j)： n");for (k=0;k<G->e;k+)/建立边表scanf("n%d,%d",&i,&j); /读入边 <Vi,Vj>的顶点对应序号s=new EdgeNode;/生成新边表结点ss->adjvex=j;/邻接点序号为js->next=G->adjlisti.firstedge; /将新边表结点s 插入

8、到顶点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;/ 标记

9、vi 已访问p=G->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;i<G->n;i+)visitedi=FALSE;for(i=0;i<G->n;i+)if(!v

10、isitedi)DFS(G,i);/*/*广度优先遍历*/*/ typedef structint front;int rear;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

11、EnQueue(CirQueue *Q,int x)if (QueueFull(Q)printf("Queue overflow");elseQ->count+;Q->dataQ->rear=x;Q->rear=(Q->rear+1)%QueueSize;精彩文档实用标准文案int DeQueue(CirQueue *Q)int temp;if(QueueEmpty(Q)printf("Queue underflow");return false;elsetemp=Q->dataQ->front;Q->co

12、unt-;Q->front=(Q->front+1)%QueueSize;return temp;void BFS(ALGraph*G,int k)/以 vk 为源点对用邻接表表示的图G进行广度优先搜索int i;CirQueue Q;/ 须将队列定义中DataType 改为 intEdgeNode *p;InitQueue(&Q);/ 队列初始化printf("visit vertex:%cn",G->adjlistk.vertex);/ 访问源点vkvisitedk=TRUE;EnQueue(&Q,k);/vk已访问，将其人队。 （实际

13、上是将其序号人队）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->adjlistp->adjvex.vertex);/ 访问 vjvisitedp->adjvex=TRUE;EnQueue(&a

14、mp;Q,p->adjvex);/ 访问过的vj 人队p=p->next;/ 找 vi 的下一邻接点精彩文档实用标准文案void BFSTraverseM(ALGraph *G)int i;for (i=0;i<G->n;i+)visitedi=FALSE;for (i=0;i<G->n;i+)if (!visitedi)BFS(G,i);/*/*主函数调用*/*/ int main()int n;ALGraph G;CreateGraphAL(&G);printf("深度优先遍历：n");DFSTraverseM(&G)

15、;printf("广度优先遍历：n");BFSTraverseM(&G);return 0;程序流程图开始访问V, 置标志求 V邻接点有邻接点 w？YW访问过？N精彩文档wVN返回Y求下一邻接点深度优先遍历流程图实用标准文案开始初始化 visitvV 入队列N!IsEmptyQueue(Q)结束Y对头元素出队，W= FirstAdjVex(G,u)N初始化 visitedvw!=-1V 入队列Yw=NextAdjVex(G,u,w)广度优先遍历流程图调试报告发现问题 ：1. 在创建图的邻接表以后，得到的深度优先遍历和自己在草稿纸上演算得到的序列不符。2. 在创建图的

16、邻接表以后，得到的广度优先遍历和自己在草稿纸上演算得到的序列不符。调试：1. 仔细检查程序后，发现是因为创建邻接表的方法是头插法；2. 检查程序，发现依据队列的长度而判断队满和队空的条件不能实现。解决方案 ：1. 我重新在草稿纸上对用头插法建立的邻接表进行深度遍历；2. 将队满的条件修改为： (rear+1)%QueueSize=front; 将队空的条件修改为： rear=front结果：结果运行正确！使用说明精彩文档实用标准文案建立邻接表深度优先遍历广度优先遍历心得体会数据结构顾名思义讲求的是一种存储结构， 一路走来先后学习了表、 树，最后学习的是图， 对于每种存储结构学习之初都会学习一些基本操作， 而操作之中又以创建和遍历为最基本的操作， 只有熟练掌握了以后才能对其他操作进行研究和学习。图的存储结构相比表和树都要复杂， 其操作过程也较难进行掌握。 仅仅是创建图的存储结构便分为矩阵、 临接链表、 十字链表等， 对于每一种存储结构又分为有向与无向之分。 然而，深度优先和广度优先是两种算法， 其算法思想并不依赖与元素的存储方式，也就