大数据结构图地基本操作.doc

word1 实验题目图的根本操作2 实验目的1)掌握图的邻接矩阵、邻接表的表示方法。2)掌握建立图的邻接矩阵的算法。3)掌握建立图的邻接表的算法。4)加深对图的理解，逐步培养解决实际问题的编程能力3需求分析(1)编写图根本操作函数。建立图的邻接表，邻接矩阵Create_Graph( LGraph lg. MGraph mg ) 邻接表表示的图的递归深度优先遍历LDFS( LGraph g, int i )邻接矩阵表示的图的递归深度优先遍历MDFS( MGraph g,int i, int vn )邻接表表示的图的广度优先遍历LBFS( LGraph g, int s, int n )邻接矩阵表示的图的广度优先遍历MBFS(MGraph g, int s, int n )(2)调用上述函数实现如下操作。建立一个图的邻接矩阵和图的邻接表。采用递归深度优先遍历输出图的邻接矩阵采用递归深度优先遍历输出图的邻接表。采用图的广度优先调历输出图的邻接表。采用图的广度优先遍历输出图的邻接矩阵4概要设计（1） ：/*图的根本操作*/- 邻接矩阵数据类型的定义-/ 最大顶点个数typedef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arum;/ 图当前顶点数和弧数MGraph ;/-邻接表数据类型的定义-typedef struct Arodeint adjvex;/ 该弧所指向的顶点的位置 struct Arode *nextarc;/ 指向下一条弧的指针 Arode;typedef struct VNodechar data;/ 顶点信息Arode *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arum;/ 图当前顶点数和弧数 LGraph;（2） 本程序主要包含6个函数： 主函数main() 建立图的邻接矩阵，邻接表 Create_Graph() 邻接表表示的图的递归深度优先遍历LDFS () 邻接矩阵表示的图的递归深度优先遍历MDFS () 邻接表表示的图的广度优先遍历LBFS() 邻接矩阵表示的图的广度优先遍历MBFS各函数间调用关系如下：mainCreate_Graph ()LDFS ()MDFS ()LBFS ()MBFS（3） 主函数的伪码main() 定义邻接矩阵和邻接表；建立邻接矩阵和邻接表；邻接矩阵MDFS深度优先遍历；邻接矩阵MBFS广度优先遍历；邻接表LDFS深度优先遍历；邻接表LBFS广度优先遍历5详细设计/*图的根本操作*/- 邻接矩阵数据类型的定义-/ 最大顶点个数typedef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arum;/ 图当前顶点数和弧数MGraph ;/-邻接表数据类型的定义-typedef struct Arodeint adjvex;/ 该弧所指向的顶点的位置 struct Arode *nextarc;/ 指向下一条弧的指针 Arode;typedef struct VNodechar data;/ 顶点信息Arode *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arum;/ 图当前顶点数和弧数 LGraph;int Create_Graph( MGraph *Mg , LGraph *Lg ) / 建立图的邻接矩阵，邻接表输入图的顶点个数字符，构造顶点向量输入图的任意两个顶点的弧构造邻接矩阵构造邻接表void LDFS(LGraph *Lg,int i) 邻接表表示的图的递归深度优先遍历显示顶点向量，指针指向下一个顶点向量下一个顶点没有被访问，继续否如此 退会上一个顶点向量的另一个边void MDFS(MGraph *Mg,int i) 邻接矩阵表示的图的递归深度优先遍历显示顶点向量，指针指向下一个顶点向量下一个顶点没有被访问，继续否如此 退会上一个顶点向量的另一个边void LBFS( LGraph *Lg )邻接表表示的图的广度优先遍历 初始化 visited初始化 队列没被访问过显示顶点向量入队出队访问下一个顶点向量void MBFS(MGraph *Mg )邻接矩阵表示的图的广度优先遍历 初始化 visited初始化 队列没被访问过显示顶点向量入队出队访问下一个顶点向量/-主函数-main() 定义邻接矩阵和邻接表；建立邻接矩阵和邻接表；邻接矩阵MDFS深度优先遍历；邻接矩阵MBFS广度优先遍历；邻接表LDFS深度优先遍历；邻接表LBFS广度优先遍历6测试结果7. 参考文献数据结构8附录#include <stdio.h>#include <malloc.h>#include <stddef.h>#include <math.h> #define OK 1#define ERROR 0#define MAX_VERTEX_NUM20/*图的根本操作*/int visitedMAX_VERTEX_NUM;/ 访问标志数组/- 邻接矩阵数据类型的定义-/ 最大顶点个数typedef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arum;/ 图当前顶点数和弧数MGraph ;/-邻接表数据类型的定义-typedef struct Arodeint adjvex;/ 该弧所指向的顶点的位置 struct Arode *nextarc;/ 指向下一条弧的指针 Arode;typedef struct VNodechar data;/ 顶点信息Arode *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arum;/ 图当前顶点数和弧数 LGraph;/_队列函数_typedef struct Queueint arryMAX_VERTEX_NUM;int front,rear;Queue;Queue Q;void InitQueue()/ 队列初始化Q.front=Q.rear=0;int QueueEmpty(Queue *Q)/ 清空队列if(Q->front=Q->rear)return 1;elsereturn 0;void EnQueue(Queue *Q,int w)/ 入队if(Q->rear+1)%MAX_VERTEX_NUM=Q->front)printf("Error!");elseQ->arryQ->rear=w;Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;int DeQueue(Queue *Q)/ 出队int u; if(Q->front=Q->rear)return -1;u=Q->front;Q->front=(Q->front+1)%MAX_VERTEX_NUM;return u;/_队列函数end_/*函数：Create_Graph*功能：建立图的邻接矩阵，邻接表 *说明：该构建的为无向网 mg 为邻接矩阵 ，lg为邻接表 , 无权值 */int Locatevex(MGraph *Mg , char v)/ 确定 v 元素在Mg中的位置int i;for(i=0;Mg->vexsi!=v;i+);if(i>Mg->vexnum)/ 输入的元素不正确如此显示 错误printf("ERROR ");return i;/ 返回位置int Create_Graph( MGraph *Mg , LGraph *Lg ) / 建立图的邻接矩阵，邻接表 int i , j , k ;char v1 , v2 ;Arode *q,*p;printf("输入图的顶点数和弧数: "); scanf("%d %d",&Mg->vexnum,&Mg->arum);getchar();Lg->vexnum=Mg->vexnum;/ 邻接表的顶点数和弧数 Lg->arum=Mg->arum;for(i=0;i<Mg->vexnum;i+)/ 构造顶点向量 printf("请输入一个图的顶点(字符):");scanf("%c" , &Mg->vexsi);getchar();Lg->verticesi.data=Mg->vexsi; / 赋值Lg->verticesi.firstarc=NULL;/ 指向第一条依附该顶点的弧的指针 为空 for(i=0;i<Mg->vexnum;i+)/ 初始化邻接矩阵for(j=0;j<Mg->vexnum;j+)Mg->acrsij=0 ;for(k=0;k<Mg->arum;k+)/ 构造邻接矩阵和邻接表printf("请输入一条边连接的2个顶点：");scanf("%c %c",&v1,&v2);getchar();i=Locatevex(Mg,v1);/ 确定 v1 在Mg 中的位置j=Locatevex(Mg,v2);/ 确定 v2 在Mg 中的位置Mg->acrsji=Mg->acrsij=1;/ 置v1,v2的对称弧v2,v1p=(Arode *)malloc(sizeof(Arode); p->adjvex=i;/ 确认顶点位置p->nextarc=Lg->verticesj.firstarc;/ 指向下一条弧的指针Lg->verticesj.firstarc=p;/ 赋值q=(Arode *)malloc(sizeof(Arode); q->adjvex=j;/ 确认顶点位置 q->nextarc=Lg->verticesi.firstarc;/ 指向下一条弧的指针Lg->verticesi.firstarc=q;/ 赋值return OK ; /*函数：LDFS*功能：邻接表表示的图的递归深度优先遍历*说明：*/int LAdjVex(LGraph *Lg,int k)/ 位置 Arode *p;for(p=Lg->verticesk.firstarc;p!=NULL;p=p->nextarc)if(!visitedp->adjvex)return p->adjvex;return -1;void LDFS(LGraph *Lg,int i) int k;visitedi=OK;printf("%c",Lg->verticesi.data);for(k=LAdjVex(Lg,i);k>=0;k=LAdjVex(Lg,k)if(!visitedk)LDFS(Lg,k);/*函数：MDFS*功能：邻接矩阵表示的图的递归深度优先遍历*说明：*/int AdjVes(MGraph *Mg,int k)/ 位置 int i;for(i=0;i<Mg->vexnum;i+)if(Mg->acrski&&(!visitedi)return i;return -1;void MDFS(MGraph *Mg,int i)/ 递归深度优先遍历int k;visitedi=1;/ 访问标志数组某位 置 1printf("%c",Mg->vexsi);/ 显示for(k=AdjVes(Mg,i);k>=0;k=AdjVes(Mg,k)if(!visitedk)MDFS(Mg,k);/ 递归/*函数：LBFS*功能：邻接表表示的图的广度优先遍历 *说明：*/void LBFS( LGraph *Lg )int i,u,w;for(i=0;i<Lg->vexnum;+i)/ 初始化 visitedvisitedi=0;InitQueue();/ 初始化 队列for(i=0;i<Lg->vexnum;+i)if(!visitedi)/ 没被访问过visitedi=1;printf("%c",Lg->verticesi.data);EnQueue(&Q,i);/ 入队while(!QueueEmpty(&Q)u=DeQueue(&Q);/ 出队for(w=LAdjVex(Lg,u);w>=0;w=LAdjVex(Lg,u)if(!visitedw)/ 没被访问过visitedw=1;printf("%c",Lg->verticesw.data);EnQueue(&Q,w);/ 入队/*函数：MBFS*功能：邻接矩阵表示的图的广度优先遍历*说明：*/void MBFS(MGraph *Mg )int i,w,u;for(i=0;i<Mg->vexnum;i+)/ 初始化 visitedvisitedi=0; InitQueue();/ 初始化队列for(i=0;i<Mg->vexnum;+i)if(!visitedi)/ 没被访问过visitedi=1;printf("%c",Mg->vexsi);/ 显示EnQueue(&Q,i);/ 入队while(!QueueEmpty(&Q)u=DeQueue(&Q);/ 出队for(w=AdjVes(Mg,u);w>=0;w=AdjVes(Mg,u) if(!visitedw)/ 没被访问过visitedw=1;printf("%c",Mg->vexsw); / 显示EnQueue(&Q,w);/ 入队/*主函数*/void main()int i ;MGraph Mg;LGraph Lg;Create_Graph( &Mg, &Lg);printf("邻接矩阵MDFS深度优先遍历：t");for(i=0;i<Mg.vexnum;i+)visitedi=0;/ 初始化 visited for(i=0;i<Mg.vexnum;i+)if(!visitedi)MDFS(&Mg,i);/ 遍历 Mgprintf("n邻接矩阵MBFS广度优先遍历：t");MBFS(&Mg) ;/ 遍历 Mgprintf("n");printf("邻接表LDFS深度优先遍历：t");for(i=0;i<Lg.vexnum;+i) visitedi=0; / 初始化 visited for(i=0;i<Lg.vexnum;+i) if(!visitedi) LDFS(&Lg,i);/ 遍历 Lgprintf("n邻接表LBFS广度优先遍历：t");LBFS(&Lg) ;/ 遍历 Lgprintf("n");须知事项：l 每位同学必须完成实验任务，并提交实验报告。杜绝抄袭和拷贝，一经发现该次实验雷同报告均以零分计。l 请将实验报告以电子文档提交，“网络工程专业请发送到fjsdwlgc163 信箱中，“电子信息专业请发送到fjsddzxx163 信箱中，请附上程序清单.C源程序文件、和实验报告WORD文档两局部，以打包压缩文件形式提交，每次实验为一个文件夹的打包压缩文件，文件夹名统一为*?.rar或*?.zip，其中*为你的学号全部，为你中文某某，?分别为01，02，0311表示第几次实验。11 / 11