实验六：图的遍历与最小生成树

《实验六：图的遍历与最小生成树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验六--图的邻接矩阵存储和最小生成树实验六图的邻接矩阵存储和最小生成树一、实验目的1．掌握图的邻接矩阵存储结构（或邻接表）2．掌握图的深度优先遍历和广度优先遍历算法2．掌握图的最小生成树算法（Prim算法）二、实验内容按下图所示无向带权图，实现以下各项功能。图1无向带权图1．用图的邻接矩阵（或者邻接表）的方式存储图1的无向带权图。2．输出该无向带权图的顶点序列以及权值集合（采用邻接矩阵存储）。3．分别采用深度优先和广度优先算法遍历该无向图4．采用Prim算法求该无向带权图的最小生成树。要求：实验后用专用实验纸书写报告。报告中要说明实验题目，内容；分析实验过程，总结实验结

2、果。三、设计指导1）创建一个头文件seqlist.h用来保存顺序表相关函数。#defineMaxSize100typedefcharDataType;Page8of8数据结构实验六--图的邻接矩阵存储和最小生成树typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;//初始化ListInitiate(L)voidListInit(SeqList*L){L->size=0;/*定义初始数据元素个数*/}//求当前数据元素个数ListLength(L)intListLength(SeqListL){returnL.size;}//插

3、入数据元素ListInsert(L,i,x)intListInsert(SeqList*L,inti,DataTypex){intj;for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];/*依次后移*/L->list[i]=x;/*插入x*/L->size++;/*元素个数加1*/return1;}//删除数据元素ListDelete(L,i,x)intListDelete(SeqList*L,inti,DataType*x){intj;*x=L->list[i];/*保存删除的元素到x中*/for(j=i+1;j<=L->size-1;j

4、++)L->list[j-1]=L->list[j];/*依次前移*/L->size--;/*数据元素个数减1*/return1;}//取数据元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i<0

5、

6、i>L.size-1){Page8of8数据结构实验六--图的邻接矩阵存储和最小生成树printf("参数i不合法!");return0;}else{*x=L.list[i];return1;}}2）创建一个头文件seqcqueue.h用来保存循环队列相关函数。#include#defineMaxQ

7、ueueSize20typedefstruct{DataTypequeue[MaxQueueSize];intrear;intfront;intcount;}SeqCQueue;//初始化QueueInit(Q)voidQueueInit(SeqCQueue*Q){Q->rear=0;Q->front=0;Q->count=0;}//非空否QueueNotEmpty(Q)intQueueNotEmpty(SeqCQueueQ){if(Q.count!=0)return1;elsereturn0;}//入队列QueueAppend(Q,x)intQueueAppend(SeqCQu

8、eue*Q,DataTypex){if(Q->count>0&&Q->rear==Q->front){printf("队列已满无法插入!");return0;}Page8of8数据结构实验六--图的邻接矩阵存储和最小生成树else{Q->queue[Q->rear]=x;Q->rear=(Q->rear+1)%MaxQueueSize;Q->count++;return1;}}//出队列QueueDelete(Q,d)intQueueDelete(SeqCQueue*Q,DataType*d){if(Q->count==0){printf("队列已空无数据元素出队列!")

9、;return0;}else{*d=Q->queue[Q->front];Q->front=(Q->front+1)%MaxQueueSize;Q->count--;return1;}}//取队头数据元素QueueGet(Q,d)intQueueGet(SeqCQueueQ,DataType*d){if(Q.count==0){printf("队列已空无数据元素可取!");return0;}else{*d=Q.queue[Q.front];return1;}}3）主函数中包含