最小生成树和最短路径大数据结构实验.docx
《最小生成树和最短路径大数据结构实验.docx》由会员分享，可在线阅读，更多相关《最小生成树和最短路径大数据结构实验.docx（22页珍藏版）》请在冰点文库上搜索。
最小生成树和最短路径大数据结构实验
实验报告
June18
2015
姓名：
陈斌学号：
E11314079专业：
13计算机科学与技术
数据结构第八次实验
学号E11314079专业计算机科学与技术姓名陈斌
实验日期2015.06.18教师签字成绩
实验报告
【实验名称】最小生成树和最短路径
【实验目的】
（1）掌握最小生成树以及最短路径的相关概念；
（2）掌握Prim算法和Kruskal算法；
（3）掌握Dijkstra算法
【实验内容】
●采用普里姆算法求最小生成树
（1）编写一个算法，对于教材图7.16（a）所示的无向带权图G采用普里姆算法输出从顶点V1出发的最小生成树。
图的存储结构自选。
（2）对于上图，采用克鲁斯卡尔算法输出该图的最小生成树。
（提示：
a.先对边按权值从小到大排序，得有序边集E；为所有顶点辅设一个数组Vset，标记各顶点所处的连通分量，初始时各不相同。
b.依次从E中取出一条边（i,j），检查顶点i和j是否属于同一连通分量，如是，则重取下一条边；否则，该边即为生成树的一条边，输出该边，同时将所有与j处于同一连通分量的顶点的Vset值都修改为与i的相同。
c.重复b步直至输出n-1条边。
）
源代码：
head.h:
#include
#include
#include//malloc（）
#include//INT,MAX
#include//EOF,NULL
#include//atoi（）
#include//eof（）
#include//floor（）,ceil（）,abs（）
#include//exit（）
#include//cout,cin
//函数结果状态代码
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
//OVERFLOW在math.h中已定义为3
typedefintStatus;
typedefintBoolean;//布尔类型
main.cpp:
#include"head.h"
typedefintVRType;
typedefcharInfoType;
#defineMAX_NAME3/*顶点字符串的最大长度+1*/
#defineMAX_INFO20/*相关信息字符串的最大长度+1*/
typedefcharVertexType[MAX_NAME];
/*图的数组（邻接矩阵）存储表示*/
#defineINFINITYINT_MAX/*用整型最大值代替∞*/
#defineMAX_VERTEX_NUM20/*最大顶点个数*/
typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图,有向网,无向图,无向网}*/
typedefstruct
{
VRTypeadj;/*顶点关系类型。
对无权图，用1（是）或0（否）表示相邻否；*/
/*对带权图，c则为权值类型*/
InfoType*info;/*该弧相关信息的指针（可无）*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/
AdjMatrixarcs;/*邻接矩阵*/
intvexnum,arcnum;/*图的当前顶点数和弧数*/
GraphKindkind;/*图的种类标志*/
}MGraph;
intLocateVex（MGraphG,VertexTypeu）
{/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
inti;
for（i=0;iif（strcmp（u,G.vexs[i]）==0）
returni;
return-1;
}
StatusCreateAN（MGraph&G）
{/*采用数组（邻接矩阵）表示法,构造无向网G*/
inti,j,k,w;
VertexTypeva,vb;
printf（"请输入无向网G的顶点数边数（用逗号隔开）:
"）;
scanf（"%d,%d",&G.vexnum,&G.arcnum）;
printf（"请输入%d个顶点的值（<%d个字符;用空格隔开）:
\n",G.vexnum,MAX_NAME）;
for（i=0;iscanf（"%s",G.vexs[i]）;
for（i=0;ifor（j=0;j{
G.arcs[i][j].adj=INFINITY;/*网*/
}
printf（"请输入%d条边的顶点1顶点2权值（用空格隔开）:
\n",G.arcnum）;
for（k=0;k{
scanf（"%s%s%d%*c",va,vb,&w）;/*%*c吃掉回车符*/
i=LocateVex（G,va）;
j=LocateVex（G,vb）;
G.arcs[i][j].adj=G.arcs[j][i].adj=w;/*无向*/
}
G.kind=AN;
returnOK;
}
typedefstruct
{/*记录从顶点集U到V-U的代价最小的边的辅助数组定义*/
VertexTypeadjvex;
VRTypelowcost;
}minside[MAX_VERTEX_NUM];
intminimum（minsideSZ,MGraphG）
{/*求closedge.lowcost的最小正值*/
inti=0,j,k,min;
while（!
SZ[i].lowcost）
i++;
min=SZ[i].lowcost;/*第一个不为0的值*/
k=i;
for（j=i+1;jif（SZ[j].lowcost>0）
if（min>SZ[j].lowcost）
{
min=SZ[j].lowcost;
k=j;
}
returnk;
}
voidMiniSpanTree_PRIM（MGraphG,VertexTypeu）
{/*用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边算法7.9*/
inti,j,k;
minsideclosedge;
k=LocateVex（G,u）;
for（j=0;j{
if（j!
=k）
{
strcpy（closedge[j].adjvex,u）;
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0;/*初始,U={u}*/
printf（"最小代价生成树的各条边为:
\n"）;
for（i=1;i{/*选择其余G.vexnum-1个顶点*/
k=minimum（closedge,G）;/*求出T的下一个结点：
第K顶点*/
printf（"（%s-%s）\n",closedge[k].adjvex,G.vexs[k]）;/*输出生成树的边*/
closedge[k].lowcost=0;/*第K顶点并入U集*/
for（j=0;jif（G.arcs[k][j].adj{/*新顶点并入U集后重新选择最小边*/
strcpy（closedge[j].adjvex,G.vexs[k]）;
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
typedefstructnode
{
intva;//边的起始顶点
intvb;//边的终止顶点
intw;//边的权值
}Edge;
intVset[MAX_VERTEX_NUM];
voidInitialize（MGraph&G）
{
for（inti=0;iVset[i]=i;
}
intSizearray（MGraphG）
{
return2*G.arcnum-1;
}
voidSwitch（Edge&b,Edgea）
{
b.va=a.va;
b.vb=a.vb;
b.w=a.w;
}
voidHeapAdjust（Edgea[],intlow,inthigh）
{//建大顶堆
inti=low;
Edgetemp;
Switch（temp,a[i]）;//先将堆顶存入temp
for（intj=2*i+1;j<=high;j=2*j+1）
{
if（jj++;
if（temp.w{//若不满足大顶堆条件，则需进行调准
Switch（a[i],a[j]）;
i=j;
}
else
break;
}
Switch（a[i],temp）;//最后确定a[i]的位置
}
voidHeapsort（Edgea[],MGraphG）
{
Edgetemp;
for（inti=Sizearray（G）/2;i>=0;--i）
HeapAdjust（a,i,Sizearray（G））;
for（i=Sizearray（G）;i>0;--i）
{
Switch（temp,a[0]）;
Switch（a[0],a[i]）;
Switch（a[i],temp）;
HeapAdjust（a,0,i-1）;
}
}
voidMiniSpanTree_Kruskal（MGraphG）
{
EdgeE[MAX_VERTEX_NUM];
intk=0;
for（inti=0;i{
for（intj=0;j{
if（G.arcs[i][j].adj!
=INFINITY）
{
E[k].va=i;
E[k].vb=j;
E[k].w=G.arcs[i][j].adj;
k++;
}
}
}
Heapsort（E,G）;
Initialize（G）;//初始化辅助数组
k=1;//生成的边数，最后要刚好为总边数
intj=0;//E中的下标
printf（"最小代价生成树的各条边及相应权值为:
\n"）;
while（k{
intsn1=Vset[E[j].va];
intsn2=Vset[E[j].vb];//得到两顶点属于的集合编号
if（sn1!
=sn2）//不在同一集合编号内的话，把边加入最小生成树
{
printf（"（%s-%s）:
%d\n",G.vexs[E[j].va],G.vexs[E[j].vb],E[j].w）;
k++;
for（i=0;iif（Vset[i]==sn2）
Vset[i]=sn1;
}
j++;
}
}
voidmain（）
{
MGraphG;
CreateAN（G）;
cout<<"--------普里姆算法输出从顶点V1出发的最小生成树--------\n"<MiniSpanTree_PRIM（G,G.vexs[0]）;
cout<<"------------------------------------------------------\n"<cout<<"--------克鲁斯卡尔算法输出从顶点V1出发的最小生成树----\n"<MiniSpanTree_Kruskal（G）;
cout<<"------------------------------------------------------"<}
运行结果：
●采用迪杰斯特拉算法求单源最短路径
编写一个算法，采用迪杰斯特拉算法，输出如下图所示的有向带权图G中从顶点a到其他各顶点的最短路径长度和最短路径。
图的存储结构自选。
源代码：
head.h:
#include
#include
#include//malloc（）
#include//INT,MAX
#include//EOF,NULL
#include//atoi（）
#include//eof（）
#include//floor（）,ceil（）,abs（）
#include//exit（）
#include//cout,cin
//函数结果状态代码
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
//OVERFLOW在math.h中已定义为3
typedefintStatus;
typedefintBoolean;//布尔类型
main.cpp:
#include"head.h"
#defineMAX_NAME5/*顶点字符串的最大长度+1*/
#defineMAX_INFO20/*相关信息字符串的最大长度+1*/
typedefintVRType;
typedefcharInfoType;
typedefcharVertexType[MAX_NAME];
/*图的数组（邻接矩阵）存储表示*/
#defineINFINITYINT_MAX/*用整型最大值代替∞*/
#defineMAX_VERTEX_NUM20/*最大顶点个数*/
typedefenum{DG,DN,AG,AN}GraphKind;/*{有向图,有向网,无向图,无向网}*/
typedefstruct
{
VRTypeadj;/*顶点关系类型。
对无权图，用1（是）或0（否）表示相邻否；*/
/*对带权图，c则为权值类型*/
InfoType*info;/*该弧相关信息的指针（可无）*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/
AdjMatrixarcs;/*邻接矩阵*/
intvexnum,arcnum;/*图的当前顶点数和弧数*/
GraphKindkind;/*图的种类标志*/
}MGraph;
typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefintShortPathTable[MAX_VERTEX_NUM];
intLocateVex（MGraphG,VertexTypeu）
{/*初始条件:
图G存在,u和G中顶点有相同特征*/
/*操作结果:
若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/
inti;
for（i=0;iif（strcmp（u,G.vexs[i]）==0）
returni;
return-1;
}
StatusCreateDN（MGraph*G）
{/*采用数组（邻接矩阵）表示法,构造有向网G*/
inti,j,k,w;
VertexTypeva,vb;
printf（"请输入有向网G的顶点数,弧数:
"）;
scanf（"%d,%d",&（*G）.vexnum,&（*G）.arcnum）;
printf（"请输入%d个顶点的值（<%d个字符）:
\n",（*G）.vexnum,MAX_NAME）;
for（i=0;i<（*G）.vexnum;++i）/*构造顶点向量*/
scanf（"%s",（*G）.vexs[i]）;
for（i=0;i<（*G）.vexnum;++i）/*初始化邻接矩阵*/
for（j=0;j<（*G）.vexnum;++j）
{
（*G）.arcs[i][j].adj=INFINITY;/*网*/
}
printf（"请输入%d条弧的弧尾弧头权值（以空格作为间隔）:
\n",（*G）.arcnum）;
for（k=0;k<（*G）.arcnum;++k）
{
scanf（"%s%s%d%*c",va,vb,&w）;/*%*c吃掉回车符*/
i=LocateVex（*G,va）;
j=LocateVex（*G,vb）;
（*G）.arcs[i][j].adj=w;/*有向网*/
}
（*G）.kind=DN;
returnOK;
}
typedefintQElemType;
/*单链队列－－队列的链式存储结构*/
typedefstructQNode
{
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront,rear;/*队头、队尾指针*/
}LinkQueue;
LinkQueueQ;
StatusInitQueue（LinkQueue*Q）
{/*构造一个空队列Q*/
（*Q）.front=（*Q）.rear=（QueuePtr）malloc（sizeof（QNode））;
if（!
（*Q）.front）
exit（OVERFLOW）;
（*Q）.front->next=NULL;
returnOK;
}
StatusQueueEmpty（LinkQueueQ）
{/*若Q为空队列,则返回TRUE,否则返回FALSE*/
if（Q.front==Q.rear）
returnTRUE;
else
returnFALSE;
}
StatusEnQueue（LinkQueue*Q,QElemTypee）
{/*插入元素e为Q的新的队尾元素*/
QueuePtrp=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）/*存储分配失败*/
exit（OVERFLOW）;
p->data=e;
p->next=NULL;
（*Q）.rear->next=p;
（*Q）.rear=p;
returnOK;
}
StatusDeQueue（LinkQueue*Q,QElemType*e）
{/*若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/
QueuePtrp;
if（（*Q）.front==（*Q）.rear）
returnERROR;
p=（*Q）.front->next;
*e=p->data;
（*Q）.front->next=p->next;
if（（*Q）.rear==p）
（*Q）.rear=（*Q）.front;
free（p）;
returnOK;
}
voidShortestPath_DIJ（MGraphG,intv0,PathMatrix*P,ShortPathTable*D）
{/*用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度*/
/*D[v]。
若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。
*/
/*final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径算法7.15*/
intv,w,i,j,min;
Statusfinal[MAX_VERTEX_NUM];
for（v=0;v{
final[v]=FALSE;
（*D）[v]=G.arcs[v0][v].adj;
for（w=0;w（*P）[v][w]=FALSE;/*设空路径*/
if（（*D）[v]{
（*P）[v][v0]=TRUE;
（*P）[v][v]=TRUE;
}
}
（*D）[v0]=0;
final[v0]=TRUE;/*初始化,v0顶点属于S集*/
for（i=1;i{/*开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集*/
min=INFINITY;/*当前所知离v0顶点的最近距离*/
for（w=0;wif（!
final[w]）/*w顶点在V-S中*/
if（（*D）[w]{
v=w;
min=（*D）[w];
}/*w顶点离v0顶点更近*/
final[v]=TRUE;/*离v0顶点最近的v加入S集*/
EnQueue（&Q,v）;
for（w=0;w{
if（!
final[w]&&min
升级会员 