《数据结构——图的基本操作(共11页).doc》由会员分享，可在线阅读，更多相关《数据结构——图的基本操作(共11页).doc（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上1 实验题目图的基本操作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, in
2、t n )邻接矩阵表示的图的广度优先遍历MBFS(MGraph g, int s, int n )(2)调用上述函数实现下列操作。建立一个图的邻接矩阵和图的邻接表。采用递归深度优先遍历输出图的邻接矩阵采用递归深度优先遍历输出图的邻接表。采用图的广度优先调历输出图的邻接表。采用图的广度优先遍历输出图的邻接矩阵4概要设计（1） ：/*图的基本操作*/- 邻接矩阵数据类型的定义-/ 最大顶点个数typedef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arcnum
3、;/ 图当前顶点数和弧数MGraph ;/-邻接表数据类型的定义-typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针 ArcNode;typedef struct VNodechar data;/ 顶点信息ArcNode *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum;/ 图当前顶点数和弧数 LGraph;（2） 本程序
4、主要包含6个函数： 主函数main() 建立图的邻接矩阵，邻接表 Create_Graph () 邻接表表示的图的递归深度优先遍历LDFS () 邻接矩阵表示的图的递归深度优先遍历MDFS () 邻接表表示的图的广度优先遍历LBFS () 邻接矩阵表示的图的广度优先遍历MBFS（）各函数间调用关系如下：mainCreate_Graph ()LDFS ()MDFS ()LBFS ()MBFS（）（3） 主函数的伪码main() 定义邻接矩阵和邻接表； 建立邻接矩阵和邻接表； 邻接矩阵MDFS深度优先遍历；邻接矩阵MBFS广度优先遍历；邻接表LDFS深度优先遍历；邻接表LBFS广度优先遍历5详细设
5、计/*图的基本操作*/- 邻接矩阵数据类型的定义-/ 最大顶点个数typedef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arcnum;/ 图当前顶点数和弧数MGraph ;/-邻接表数据类型的定义-typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针 ArcNode;typedef struct VNodechar data;/ 顶点信息Arc
6、Node *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum;/ 图当前顶点数和弧数 LGraph;int Create_Graph( MGraph *Mg , LGraph *Lg ) / 建立图的邻接矩阵，邻接表输入图的顶点个数（字符），构造顶点向量输入图的任意两个顶点的弧构造邻接矩阵构造邻接表void LDFS(LGraph *Lg,int i) 邻接表表示的图的递归深度优先遍历显示顶点向量，指针指向下一个顶点向量下一个顶点没有被
7、访问，继续否则 退会上一个顶点向量的另一个边void MDFS(MGraph *Mg,int i) 邻接矩阵表示的图的递归深度优先遍历显示顶点向量，指针指向下一个顶点向量下一个顶点没有被访问，继续否则 退会上一个顶点向量的另一个边void LBFS( LGraph *Lg )邻接表表示的图的广度优先遍历 初始化 visited初始化 队列没被访问过显示顶点向量入队出队访问下一个顶点向量void MBFS(MGraph *Mg )邻接矩阵表示的图的广度优先遍历 初始化 visited初始化 队列没被访问过显示顶点向量入队出队访问下一个顶点向量/-主函数-main() 定义邻接矩阵和邻接表； 建立
8、邻接矩阵和邻接表； 邻接矩阵MDFS深度优先遍历；邻接矩阵MBFS广度优先遍历；邻接表LDFS深度优先遍历；邻接表LBFS广度优先遍历6测试结果7. 参考文献数据结构8附录#include #include #include #include #define OK 1#define ERROR 0#define MAX_VERTEX_NUM20/*图的基本操作*/int visitedMAX_VERTEX_NUM;/ 访问标志数组/- 邻接矩阵数据类型的定义-/ 最大顶点个数typedef structchar vexsMAX_VERTEX_NUM;/ 顶点向量 intacrsMAX_VERT
9、EX_NUMMAX_VERTEX_NUM;/ 邻接矩阵 intvexnum,arcnum;/ 图当前顶点数和弧数MGraph ;/-邻接表数据类型的定义-typedef struct ArcNodeint adjvex;/ 该弧所指向的顶点的位置 struct ArcNode *nextarc;/ 指向下一条弧的指针 ArcNode;typedef struct VNodechar data;/ 顶点信息ArcNode *firstarc;/ 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;
10、int vexnum,arcnum;/ 图当前顶点数和弧数 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
11、(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 元素
12、在Mg中的位置int i;for(i=0;Mg-vexsi!=v;i+);if(iMg-vexnum)/ 输入的元素不正确则显示 错误printf(ERROR );return i;/ 返回位置int Create_Graph( MGraph *Mg , LGraph *Lg ) / 建立图的邻接矩阵，邻接表 int i , j , k ;char v1 , v2 ;ArcNode *q,*p;printf(输入图的顶点数和弧数: ); scanf(%d %d,&Mg-vexnum,&Mg-arcnum);getchar();Lg-vexnum=Mg-vexnum;/ 邻接表的顶点数和弧数 L
13、g-arcnum=Mg-arcnum;for(i=0;ivexnum;i+)/ 构造顶点向量 printf(请输入一个图的顶点(字符):);scanf(%c , &Mg-vexsi);getchar();Lg-verticesi.data=Mg-vexsi; / 赋值Lg-verticesi.firstarc=NULL;/ 指向第一条依附该顶点的弧的指针 为空 for(i=0;ivexnum;i+)/ 初始化邻接矩阵for(j=0;jvexnum;j+)Mg-acrsij=0 ;for(k=0;karcnum;k+)/ 构造邻接矩阵和邻接表printf(请输入一条边连接的2个顶点：);scan
14、f(%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=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=i;/ 确认顶点位置p-nextarc=Lg-verticesj.firstarc;/ 指向下一条弧的指针Lg-verticesj.firstarc=p;/ 赋值q=(ArcNode *)malloc(sizeof(ArcNode);
15、q-adjvex=j;/ 确认顶点位置 q-nextarc=Lg-verticesi.firstarc;/ 指向下一条弧的指针Lg-verticesi.firstarc=q;/ 赋值return OK ; /*函数：LDFS*功能：邻接表表示的图的递归深度优先遍历*说明：*/int LAdjVex(LGraph *Lg,int k)/ 位置 ArcNode *p;for(p=Lg-verticesk.firstarc;p!=NULL;p=p-nextarc)if(!visitedp-adjvex)return p-adjvex;return -1;void LDFS(LGraph *Lg,in
16、t 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;ivexnum;i+)if(Mg-acrski&(!visitedi)return i;return -1;void MDFS(MGraph *Mg,int i)/ 递归深度优先遍历int k;visit
17、edi=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;ivexnum;+i)/ 初始化 visitedvisitedi=0;InitQueue();/ 初始化 队列for(i=0;ivexnum;+i)if(!visitedi)/ 没被访问过visitedi=1;printf(%c,L
18、g-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;ivexnum;i+)/ 初始化 visitedvisitedi=0
19、; InitQueue();/ 初始化队列for(i=0;ivexnum;+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;L
20、Graph Lg;Create_Graph( &Mg, &Lg);printf(邻接矩阵MDFS深度优先遍历：t);for(i=0;iMg.vexnum;i+)visitedi=0;/ 初始化 visited for(i=0;iMg.vexnum;i+)if(!visitedi)MDFS(&Mg,i);/ 遍历 Mgprintf(n邻接矩阵MBFS广度优先遍历：t);MBFS(&Mg) ;/ 遍历 Mgprintf(n);printf(邻接表LDFS深度优先遍历：t);for(i=0;iLg.vexnum;+i) visitedi=0; / 初始化 visited for(i=0;iLg.ve
21、xnum;+i) if(!visitedi) LDFS(&Lg,i);/ 遍历 Lgprintf(n邻接表LBFS广度优先遍历：t);LBFS(&Lg) ;/ 遍历 Lgprintf(n);注意事项：l 每位同学必须完成实验任务，并提交实验报告。杜绝抄袭和拷贝，一经发现该次实验雷同报告均以零分计。l 请将实验报告以电子文档提交， “网络工程”专业请发送到fjsdwlgc信箱中，“电子信息”专业请发送到fjsddzxx 信箱中，请附上程序清单.C源程序文件、和实验报告WORD文档两部分，以打包压缩文件形式提交，每次实验为一个文件夹的打包压缩文件，文件夹名统一为*?.rar或*?.zip，其中*为你的学号（全部号码），为你中文姓名，?分别为01，02，0311表示第几次实验。专心-专注-专业