(1)Prim
算法如下,头文件:
#defineINFINITY10000
#defineMAX_VERTEX_NUM20
typedefintInfoType;
typedefcharVertexType;
typedefintVRType;
typedefenum...{DG,DN,UDG,UDN}GraphKind;
typedefstructArcCell...{
VRTypeadj;
InfoType*info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct...{
VertexTypevexs[MAX_VERTEX_NUM];
AdjMatrixarcs;
intvexnum,arcnum;
GraphKindkind;
}MGraph;
intweight[][6]=...{
...{0,6,1,5,INFINITY,INFINITY},
...{6,0,5,INFINITY,3,INFINITY},
...{1,5,0,5,6,4},
...{5,INFINITY,5,0,INFINITY,2},
...{INFINITY,3,6,INFINITY,0,6},
...{INFINITY,INFINITY,4,2,6,0}
};
//#defineINPUT1
typedefstruct...{
intparent;
intcost;
}mst_prim_closedge;
源文件:
#include"graph.h"
#include"stdio.h"
#include"stdlib.h"
voidcreateDG(MGraph&g)...{}
voidcreateDN(MGraph&g)...{}
voidcreateUDG(MGraph&g)...{}
intlocate(MGraphg,charname)...{
for(inti=0;i<g.vexnum;i++)...{
if(name==g.vexs[i])...{
returni;
}
}
return-1;
}
voidcreateUDN(MGraph&g)...{
#ifdefINPUT
printf("inputthenumberofvertexandarcs: ");
scanf("%d%d",&g.vexnum,&g.arcnum);
fflush(stdin);
#else
printf("inputthenumberofvertex: ");
scanf("%d",&g.vexnum);
fflush(stdin);
#endif
inti=0,j=0,k=0;
printf("inputthenameofvertex: ");
for(i=0;i<g.vexnum;i++)...{
scanf("%c",&g.vexs[i]);
fflush(stdin);
}
for(i=0;i<g.vexnum;i++)...{
for(j=0;j<g.vexnum;j++)...{
g.arcs[i][j].adj=INFINITY;
g.arcs[i][j].info=NULL;
}
}
#ifdefINPUT
charv1,v2;
intw;
printf("inputthe%darcsv1v2andweight: ",g.arcnum);
for(k=0;k<g.arcnum;k++)...{
scanf("%c%c%d",&v1,&v2,&w);
fflush(stdin);
i=locate(g,v1);
j=locate(g,v2);
g.arcs[i][j].adj=w;
}
#else
printf("nowconstructingthematrixofgraph... ");
for(i=0;i<g.vexnum;i++)...{
for(j=0;j<g.vexnum;j++)...{
g.arcs[i][j].adj=weight[i][j];
}
}
#endif
}
voidprintGraph(MGraphg)...{
for(inti=0;i<g.vexnum;i++)...{
for(intj=0;j<g.vexnum;j++)...{
printf("%d ",g.arcs[i][j].adj);
}
printf(" ");
}
}
voidcreateGragh(MGraph&g)...{
printf("pleaseinputthetypeofgraph: ");
scanf("%d",&g.kind);
switch(g.kind)...{
caseDG:
createDG(g);
break;
caseDN:
createDN(g);
break;
caseUDG:
createUDG(g);
break;
caseUDN:
createUDN(g);
printGraph(g);
break;
}
}
//getthemincostvertice,returntheindex
intminimum(mst_prim_closedge*closedge,intn)...{
intret=-1;
intretcost=INFINITY;
for(inti=0;i<n;i++)...{
if(closedge[i].cost>0&&closedge[i].cost<retcost)...{
ret=i;
retcost=closedge[i].cost;
}
}
returnret;
}
/**//**
*theprimalgorithmofmst(minimumcostspanningtree)
*MGraphg:thegraph
*charstart:thestartpoint
*/
voidmst_prim(MGraphg,charstart)...{
mst_prim_closedge*closedge=
(mst_prim_closedge*)malloc(sizeof(mst_prim_closedge)*g.vexnum);
//gettheindexofstart
intindex=locate(g,start);
//inittheclosestedgearray
inti=0;
for(;i<g.vexnum;i++)...{
closedge[i].parent=index;
closedge[i].cost=g.arcs[index][i].adj;
}
//choosethenextn-1vertex
printf("nowthemstis: ");
intj=0;
for(i=1;i<g.vexnum;i++)...{
j=minimum(closedge,g.vexnum);
printf("%c,%c,%d ",
g.vexs[closedge[j].parent],g.vexs[j],closedge[j].cost);
//jjointheU
closedge[j].cost=0;
//updatetheclosedge
for(intk=0;k<g.vexnum;k++)...{
if(g.arcs[j][k].adj>0&&
g.arcs[j][k].adj<closedge[k].cost)...{
closedge[k].cost=g.arcs[j][k].adj;
closedge[k].parent=j;
}
}
}
}
voidmain()...{
MGraphg;
createGragh(g);
charstart;
printf("inputthestartpointofmst: ");
scanf("%c",&start);
mst_prim(g,start);
}
程序的执行结果为:
pleaseinputthetypeofgraph:
3
inputthenumberofvertex:
6
inputthenameofvertex:
a
b
c
d
e
f
nowconstructingthematrixofgraph...
06151000010000
60510000310000
150564
51000050100002
10000361000006
10000100004260
inputthestartpointofmst:
a
nowthemstis:
a,c,1
c,f,4
f,d,2
c,b,5
b,e,3
Pressanykeytocontinue
算法的复杂度:从函数mst_prim()可知,时间复杂度为O(n*n),适用于求边稠密的network的mst。
(2)Kruskal
时间复杂度为O(e*log(e)),适用于求边稀疏的network的mst。
算法思想:“等价类,并查集,边排序,选小边”。
代码如下,头文件添加:
typedefstruct...{
intv1;
intv2;
intcost;
intused;
}mst_kruskal_edge;
源文件添加:
//gettheclassofi
intfindparent(int*parent,inti)...{
while(parent[i]!=-1)...{
i=parent[i];
}
returni;
}
//getthesmallestedgethathasnotused
intgetMin(mst_kruskal_edge*edge,intnum)...{
intcost=INFINITY,index=-1;
for(inti=0;i<num;i++)...{
if(edge[i].used==0&&edge[i].cost<cost)...{
cost=edge[i].cost;
index=i;
}
}
returnindex;
}
/**//**
*thekruskalofmst
*/
voidmst_kruskal(MGraphg)...{
//firstconstructtheedgearray
mst_kruskal_edge*edge=(mst_kruskal_edge*)
malloc(sizeof(mst_kruskal_edge)*g.vexnum/2*(g.vexnum-1));
inti,j,k=0;
for(i=0;i<g.vexnum;i++)...{
for(j=i+1;j<g.vexnum;j++)...{
if(g.arcs[i][j].adj>0&&g.arcs[i][j].adj!=INFINITY)...{
edge[k].v1=i;
edge[k].v2=j;
edge[k].cost=g.arcs[i][j].adj;
//thisedgeisnotused
edge[k].used=0;
k++;
}
}
}
printf("thenumofedgeis:%d ",k);
//theparentarray,representtheclassofthevertice
int*parent=(int*)malloc(sizeof(int)*g.vexnum);
//inititwith-1
for(i=0;i<g.vexnum;i++)...{
parent[i]=-1;
}
//constructthemst
printf("nowconstructingthemst... ");
for(i=0;i<k;i++)...{
intindex=getMin(edge,k);
if(index!=-1)...{
intp1=findparent(parent,edge[index].v1);
intp2=findparent(parent,edge[index].v2);
if(p1!=p2)...{
printf("%c,%c,%d ",
g.vexs[edge[index].v1],g.vexs[edge[index].v2],edge[index].cost);
parent[p2]=p1;
}
edge[index].used=1;
}else...{
break;
}
}
}
voidmain()...{
MGraphg;
createGragh(g);
/**//*
charstart;
printf("inputthestartpointofmst: ");
scanf("%c",&start);
mst_prim(g,start);
*/
mst_kruskal(g);
}
程序的执行结果为:
pleaseinputthetypeofgraph:
3
inputthenumberofvertex:
6
inputthenameofvertex:
a
b
c
d
e
f
nowconstructingthematrixofgraph...
06151000010000
60510000310000
150564
51000050100002
10000361000006
10000100004260
thenumofedgeis:10
nowconstructingthemst...
a,c,1
d,f,2
b,e,3
c,f,4
b,c,5
Pressanykeytocontinue
说明:kruskal至多对e条边各扫描一次,上面的查找算法的复杂度是O(e),所以实现的kruskal的复杂度是O(e*e)。但是如果使用堆排序,每次的查找复杂度可以变成O(log(e))(第一次需要O(e)来建立堆),从而Kruskal的复杂度是O(e * log(e))。
分享到:
相关推荐
头歌数据结构图的最小生成树算法 第1关求图(邻接矩阵存储)最小生成树的普里姆(Prim)算法 第2关求图(邻接表存储)最小生成树的普里姆(Prim)算法 第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)...
最小生成树的构造,以及求最小生成树的 普利姆算法和克鲁斯卡尔算法,C++实现算法
如何以最低的经济代价建设这个通信网,是一个网的最小生成树问题 2、利用克鲁斯卡尔算法求网的最小生成树; 3、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列; 4、输入为存在边的顶点对,以及它们之间...
最小生成树问题算法的编程实现. 用c++的语法实现图存储结构,实现最小生成树的算法,数据结构中的经典算法。
利用克鲁斯卡尔算法求网的最小生成树。要求:若要在n各城市之间建设通信网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网络,是一个网的最小生成树问题。
最小生成树…… c++ …… 数据结构……
数据结构 最小生成树 源代码
最小生成树的代码表现方法,构造带权无向图G6的最小生成树。构造带权无向图的最小生成树。
数据结构课设<最小生成树问题>cpp含实验报告 数据结构课设<最小生成树问题>cpp含实验报告 数据结构课设<最小生成树问题>cpp含实验报告 打包下载 打包下载
用字符文件提供数据建立连通带权网络邻接矩阵存储¬¬结构。编写程序,用Prim算法求一棵最小生成树。要求输出最小生成树的各条边(用顶点无序偶表示)、各条边上的权值、最小生成树所有边上的权值之和。
天大数据结构课 作业 编译通过 好用 源代码
用C++编写 数据结构 中求最小生成树 用C++编写 数据结构 求最小生成树
数据结构实现最小生成树算法.。。。。。。。。。。。。。。。。。
一个完整的数据结构课程设计,使用qt编写,有完整的工程文件和文档,可直接下载使用。
用Prim算法构造一颗最小生成树 (2) 实验原理: ①从网中任一顶点开始,先把该顶点包含在生成树中,此时生成树只有 一个顶点。 ②找出一个端点在生成树中另一端点在生成树外的所有边,并把权值最 小的边连到同它所...
问题描述:给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。基本要求:1、城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义...
数据结构最小生成树算法实现 克鲁斯卡尔算法 帕里姆算法 文本计算小工具
源代码+报告! 0.图的创建,1.显示该图的邻接矩阵2.求树图中任意结点的度3.插入顶点4.删除顶点 5.插入边 6.删除边 7.广度优先遍历输出 8.深度优先遍历输出 9.创建最小生成树10.退出程序
连通网的最小生成树的prime和Kruskal算法,完整的测试代码,包括图的基本操作代码(详见:http://download.csdn.net/detail/u013071074/7445893),包括两组测试数据。 prime和Kruskal算法介绍详见博文:...
数据结构课程设计报告最小生成树Kruskal算法