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

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

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

2、seqlist.h用来保存顺序表相关函数。#defineMaxSize100typedefcharDataType;typedefstructDataTypelist[MaxSize];intsize;}ScqList;//初始化Listinitiate(L)voidListlnit(SeqList氺L){I->size=0;/*定义初始数据元素个数*/}//求当前数据元素个数ListLength(L)intListLength(SeqListL){returnL.size;}//插入数据元素ListInsert(L,i，x)intListInsert(SeqList

3、氺I、，inti,DataTypex){intj;for(j=L->size;j>i;j—)L->list[j]=L-〉list[j-l];/*依次后移*/L->1ist[i]=x;/*插入x*/L->sizc++；/*元素个数加1*/return1;}//删除数据元素ListDelete(L,i,x)intListDclctc(SeqList*L,inti,DataType氺x){intj;*x=L->list[i];/*保存删除的元素到x中吟for(j=i+1;j<=L->size~l;j++)L->list[j-l]=L->list[j];/*依次前移*/L->

4、size—;/*数据元素个数减1*/return1;}//取数据元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType氺x)printf(〃参数i不合法！");return0;else{本x=L.list[i];return1;}}2)创建一个头文件scqcqucuc.h用来保存循环队列相关函数。#include#defineMaxQueueSize20typedefstruct{DataTypequeue[MaxQueueSize];intrear;intfront;intcount;}ScqCQuc

5、uc;//初始化Queuelnit(Q)voidQueuelnit(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(SeqCQueue*Q，DataTypex){if(Q->count>0&&Q-〉rear==Q->front){printf(〃队列已满无法插入！〃);return0

6、;else{Q->queue[Q->rear]=x;Q-〉rear=(Q->rear+1)%MaxQueueSize;Q->count++;return1;}}//出队列QucucDclctc(Q,d)intQueueDelete(SeqCQueueDataType*d){if(Q->count==0){printf(〃队列已空无数据元素出队列！〃);return0;}else{*d=Q->queue[Q->front];Q->front=(Q->front+1)%MaxQueueSize;Q->count--;return1;}}//取队头数据元素QucucGc

7、t(Q,d)intQueueGet(SeqCQueueQ,DataType氺d){if(Q.count==0){printf(〃队列已空无数据元素可取！〃)；return0;}else{*d=Q.queue[Q.front];return1;}}2)主函数中包含的部分函数#indude#includc^include"SeqList.h"#includez，SeqCQueue.h/z#defineMaxWeight10000#defineMaxVertices10typedefcharVerT;//图的结构体