西安电子科技大学离散数学大作业Word下载.docx
《西安电子科技大学离散数学大作业Word下载.docx》由会员分享，可在线阅读，更多相关《西安电子科技大学离散数学大作业Word下载.docx（21页珍藏版）》请在冰点文库上搜索。
kruskal算法分e步,其中e是网络中边数目。
按花费递增次序来考虑这e条边,每次考虑一条边。
当考虑某条边时,若将其加入到已选边集合中会出现环路,则将其抛弃,不然,将它选入。
该算法时间复杂度为O（elge）;
Kruskal算法时间关键取决于边数,它较适合于稀疏图。
Kruskal算法结构最小生成树过程图解:
Prim算法
Prim算法能够说是全部MST算法中最简单,比较适适用于稠密图。
以图中任意一个顶点S开始,选择与之相关连边中权值最小边加入到MST中,假设这条边终点为T,则MST初始化为（S,T）,称之为“目前MST”。
接下来在剩下边中选择与目前MST中s全部顶点相关连边中权值最小边,并添加到目前MST中。
这一过程一直迭代到图中全部顶点都添加到MST中为止。
从连通网络N={V,E}中某一顶点u0出发,选择与它关联含有最小权值边（u0,v）,将其顶点加入到生成树顶点集合U中。
以后每一步从一个顶点在U中,而另一个顶点不在U中各条边中选择权值最小边（u,v）,把该边加入到生成树边集TE中,把它顶点加入到集合U中。
如此反复实施,直到网络中全部顶点都加入到生成树顶点集合U中为止。
假设G=（V,E）是一个含有n个顶点带权无向连通图,T（U,TE）是G最小生成树,其中U是T顶点集,TE是T边集。
prim算法适合稠密图,其时间复杂度为O（n^2）,其时间复杂度与边得数目无关,而kruskal算法时间复杂度为O（eloge）跟边数目相关,适合稀疏图。
二、最小生成树实现
Kruskal算法关键部分实现
Kruskal算法计算步骤大致以下:
1.将无向图边按距离长短递增式排序,放到集合中
2.遍历该集合,找出最短边,加入到结果生成树集合中
3.假如结果生成树出现回路,则放弃这条边
4.重新实施步骤2,直至全部顶点被遍历
能够看出在每次遍历过程中采取了贪心算法
Kruskal算法代码以下:
//**********************最小生成树kruscal算法*******************
intacrvisited[100];
//kruscal弧标识数组
intfind（intacrvisited[],intf）
{
while（acrvisited[f]>
0）
f=acrvisited[f];
returnf;
}
voidkruscal_arc（MGraph_LG,algraphgra）
edgedgs[20];
inti,j,k=0;
for（i=0;
i!
=G.vexnum;
++i）
for（j=i;
j!
++j）
if（G.arcs[i][j].adj!
=10000）
{
edgs[k].pre=i;
edgs[k].bak=j;
edgs[k].weight=G.arcs[i][j].adj;
++k;
}
intx,y,m,n;
intbuf,edf;
=gra.arcnum;
acrvisited[i]=0;
for（j=0;
=G.arcnum;
m=10000;
if（edgs[i].weight<
m）
m=edgs[i].weight;
x=edgs[i].pre;
y=edgs[i].bak;
n=i;
buf=find（acrvisited,x）;
edf=find（acrvisited,y）;
edgs[n].weight=10000;
if（buf!
=edf）
acrvisited[buf]=edf;
cout<
<
"
（"
x<
"
y<
）"
m;
endl;
//**************************************************************
Prim算法关键部分实现
Prim算法计算步骤大致如:
（1）初始状态,TE为空,U={v0},v0∈V;
（2）在全部u∈U,v∈V-U边（u,v）∈E中找一条代价最小边（u′,v′）并入TE,同时将v′并入U;
反复实施步骤
（2）n-1次,直到U=V为止。
Prim算法代码以下:
//**********************最小生成树PRIM算法*******************
typedefstruct
intadjvex;
intlowcost;
}closedge;
intprim（intg[][max],intn）//最小生成树PRIM算法
intlowcost[max],prevex[max];
//LOWCOST[]存放目前集合U分别到剩下结点最短路径
//prevex[]存放最短路径在U中结点
inti,j,k,min;
for（i=2;
i<
=n;
i++）//n个顶点,n-1条边
lowcost[i]=g[1][i];
//初始化
prevex[i]=1;
//顶点未加入到最小生成树中
lowcost[1]=0;
//标志顶点1加入U集合
i++）//形成n-1条边生成树
min=inf;
k=0;
for（j=2;
j<
j++）//寻求满足边一个顶点在U,另一个顶点在V最小边
if（（lowcost[j]<
min）&
&
（lowcost[j]!
=0））
min=lowcost[j];
k=j;
printf（"
（%d,%d）%d\t"
prevex[k]-1,k-1,min）;
lowcost[k]=0;
//顶点k加入U
j++）//修改由顶点k到其她顶点边权值
if（g[k][j]<
lowcost[j]）
lowcost[j]=g[k][j];
prevex[j]=k;
\n"
）;
return0;
三、代码
#include<
stdio.h>
#include<
iostream>
malloc.h>
usingnamespacestd;
#defineint_max10000
#defineinf9999
#definemax20
//**********************邻接矩阵定义*************************
typedefstructArcCell
intadj;
char*info;
}ArcCell,AdjMatrix[max][max];
charvexs[max];
AdjMatrixarcs;
intvexnum,arcnum;
}MGraph_L;
//***********************************************************
intlocalvex（MGraph_LG,charv）//返回V位置
inti=0;
while（G.vexs[i]!
=v）
++i;
returni;
intcreatMGraph_L（MGraph_L&
G）//创建图用邻接矩阵表示
charv1,v2;
inti,j,w;
cout<
请输入图顶点和弧个数:
比如46（4表示顶点个数,5表示弧个数）"
cin>
>
G.vexnum>
G.arcnum;
输入顶点"
G.vexs[i];
G.arcs[i][j].adj=int_max;
G.arcs[i][j].info=NULL;
for（intk=0;
k!
++k）
输入一条边依附顶点和权:
比如abc（a,b表示顶点,c表示权）"
cin>
v1>
v2>
w;
//输入一条边依附两点及权值
i=localvex（G,v1）;
//确定顶点V1和V2在图中位置
j=localvex（G,v2）;
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
图G邻接矩阵创建成功!
"
returnG.vexnum;
intvisited[max];
//访问标识
intwe;
typedefstructarcnode//弧结点
//该弧指向顶点位置
structarcnode*nextarc;
//弧尾相同下一条弧
//该弧信息
}arcnode;
typedefstructvnode//邻接链表顶点头接点
chardata;
//结点信息
arcnode*firstarc;
//指向第一条依附该结点弧指针
}vnode,adjlist;
typedefstruct//图定义
adjlistvertices[max];
intkind;
}algraph;
typedefstructacr
intpre;
//弧一结点
intbak;
//弧另一结点
intweight;
//弧权
}edg;
intcreatadj（algraph&
gra,MGraph_LG）//用邻接表存放图
inti=0,j=0;
arcnode*arc,*tem,*p;
gra.vertices[i].data=G.vexs[i];
gra.vertices[i].firstarc=NULL;
if（gra.vertices[i].firstarc==NULL）
=int_max&
=G.vexnum）
arc=（arcnode*）malloc（sizeof（arcnode））;
arc->
adjvex=j;
gra.vertices[i].firstarc=arc;
nextarc=NULL;
p=arc;
++j;
while（G.arcs[i][j].adj!
tem=（arcnode*）malloc（sizeof（arcnode））;
tem->
gra.vertices[i].firstarc=tem;
nextarc=arc;
arc=tem;
--j;
else
p->
gra.vexnum=G.vexnum;
gra.arcnum=G.arcnum;
return1;
intfirstadjvex（algraphgra,vnodev）//返回依附顶点V第一个点
//即以V为尾第一个结点
if（v.firstarc!
=NULL）
returnv.firstarc->
adjvex;
intnextadjvex（algraphgra,vnodev,intw）//返回依附顶点V相对于W下一个顶点
arcnode*p;
p=v.firstarc;
while（p!
=NULL&
p->
adjvex!
=w）
p=p->
nextarc;
if（p->
adjvex==w&
nextarc!
returnp->
nextarc==NULL）
return-10;
//*********************主函数***********************************
intmain（）
algraphgra;
MGraph_LG;
inti,d,g[20][20];
chara='
a'
;
d=creatMGraph_L（G）;
creatadj（gra,G）;
vnodev;
*************菜单*************"
endl<
0、最小生成树PRIM算法"
1、最小生成树KRUSCAL算法"
ints;
chary='
y'
while（y='
）
请选择菜单:
s;
switch（s）
case0:
for（i=0;
for（intj=0;
g[i+1][j+1]=G.arcs[i][j].adj;
prim:
prim（g,d）;
break;
case1:
kruscal:
kruscal_arc（G,gra）;
输入y返回菜单,输入n退出菜单y/n:
y;
if（y=='
n'
system（"
pause"
四、输出结果
Kruskal算法结果
升级会员 