文档文库
手机版
投诉建议
热门搜索： 心得体会 演讲稿 思想汇报
首页 > 西安电子科技大学离散数学大作业-

西安电子科技大学离散数学大作业-

发布时间：   来源：文档文库   
小 中 大
字号：
手机查看
离散数学大作业


离散数学大作业


班级：021231 学号：02123120 姓名：





题目：编程实现赋权有向图的最小生成树


摘要
求解图的最小生成树有三种算法，分别为Prim算法、Kruskal算法和Boruvka算法。这三种算法都是贪心算法。所以本次实验分别使用Kruskal算法和Prim算法实现赋权有向图的最小生成树。
Kruskal算法基本思想为：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。具体作法如下：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。
Prim算法基本思想是：首先选取图中任意一个顶点 v 作为生成树的根，之后继续往生成树中添加顶点 w，则在顶点 w 和顶点 v 之间必须有边，且该边上的权值应在所有和 v 相邻接的边中属最小。


关键词： 邻接矩阵；邻接表；Kruskal算法；Prim算法；最小生成树


1



一、最小生成树的研究进展
最小生成树可以使用Kruskal算法和Prim算法。下面具体介绍这两种算法。
Kruskal算法
求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n条边）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
该算法的时间复杂度为O(elge;Kruskal算法的时间主要取决于边数,它较适合于稀疏图。
Kruskal算法构造最小生成树的过程图解:
2

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算法******************* int acrvisited[100];//kruscal弧标记数组 int find(int acrvisited[],int f {
while(acrvisited[f]>0 f=acrvisited[f]; return f; }
void kruscal_arc(MGraph_L G,algraph gra {
edg edgs[20]; int i,j,k=0;
3

for(i=0;i!=G.vexnum;++i for(j=i;j!=G.vexnum;++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; } }
int x,y,m,n; int buf,edf;
for(i=0;i!=gra.arcnum;++i acrvisited[i]=0;
for(j=0;j!=G.arcnum;++j {
m=10000;
for(i=0;i!=G.arcnum;++i {
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; cout<<endl; } } }
//************************************************************** 4

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算法******************* typedef struct {
int adjvex; int lowcost; }closedge;
int prim(int g[][max],int n //最小生成树PRIM算法 {
int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径
//prevex[]存储最短路径在U中的结点 int i,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集合 for(i=2;i<=n;i++ //形成n-1条边的生成树 {
min=inf; k=0;
for(j=2;j<=n;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 for(j=2;j<=n;j++ //修改由顶点k到其他顶点边的权值 if(g[k][j]<lowcost[j] {
lowcost[j]=g[k][j]; prevex[j]=k;
5

}
printf("\n"; }
return 0; }
//************************************************************** 三、代码
#include #include #include using namespace std; #define int_max 10000 #define inf 9999 #define max 20 //**********************邻接矩阵定义************************* typedef struct ArcCell {
int adj; char *info;
}ArcCell,AdjMatrix[max][max]; typedef struct {
char vexs[max]; AdjMatrix arcs; int vexnum,arcnum; }MGraph_L;
//*********************************************************** int localvex(MGraph_L G,char v//返回V的位置 {
int i=0;
while(G.vexs[i]!=v ++i;
return i; }
int creatMGraph_L(MGraph_L &G//创建图用邻接矩阵表示 {
char v1,v2; int i,j,w;
cout<<"请输入图的顶点和弧的个数:例如4 6 (4表示顶点的个数，5表示弧的个数"<<endl;
cin>>G.vexnum>>G.arcnum; for(i=0;i!=G.vexnum;++i

6
{
cout<<"输入顶点"<<i<<endl; cin>>G.vexs[i]; }
for(i=0;i!=G.vexnum;++i for(j=0;j!=G.vexnum;++j {
G.arcs[i][j].adj=int_max; G.arcs[i][j].info=NULL; }
for(int k=0;k!=G.arcnum;++k {
cout<<"输入一条边依附的顶点和权:例如a b c (a,b表示顶点，c表示权"<<endl;
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; }
cout<<"图G邻接矩阵创建成功！"<<endl; return G.vexnum; }

int visited[max];//访问标记 int we;
typedef struct arcnode//弧结点 {
int adjvex;//该弧指向的顶点的位置
struct arcnode *nextarc;//弧尾相同的下一条弧 char *info;//该弧信息 }arcnode;
typedef struct vnode//邻接链表顶点头接点 {
char data;//结点信息
arcnode *firstarc;//指向第一条依附该结点的弧的指针 }vnode,adjlist;
typedef struct//图的定义 {
adjlist vertices[max]; int vexnum,arcnum; int kind; }algraph;


7
typedef struct acr {
int pre;//弧的一结点 int bak;//弧另一结点 int weight;//弧的权 }edg;
int creatadj(algraph &gra,MGraph_L G//用邻接表存储图 {
int i=0,j=0;
arcnode *arc,*tem,*p; for(i=0;i!=G.vexnum;++i {
gra.vertices[i].data=G.vexs[i]; gra.vertices[i].firstarc=NULL; }
for(i=0;i!=G.vexnum;++i {
for(j=0;j!=G.vexnum;++j {
if(gra.vertices[i].firstarc==NULL {
if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum {
arc=(arcnode *malloc(sizeof(arcnode; arc->adjvex=j;
gra.vertices[i].firstarc=arc; arc->nextarc=NULL; p=arc; ++j;
while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum {
tem=(arcnode *malloc(sizeof(arcnode; tem->adjvex=j; gra.vertices[i].firstarc=tem; tem->nextarc=arc; arc=tem; ++j; } --j; } } else {
if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum

8
{
arc=(arcnode *malloc(sizeof(arcnode; arc->adjvex=j; p->nextarc=arc; arc->nextarc=NULL; p=arc; } } } }
gra.vexnum=G.vexnum; gra.arcnum=G.arcnum; return 1; }

int firstadjvex(algraph gra,vnode v//返回依附顶点V的第一个点 //即以V为尾的第一个结点 {
if(v.firstarc!=NULL
return v.firstarc->adjvex; }
int nextadjvex(algraph gra,vnode v,int w//返回依附顶点V的相对于W的下一个顶点 {
arcnode *p; p=v.firstarc;
while(p!=NULL&&p->adjvex!=w {
p=p->nextarc; }
if(p->adjvex==w&&p->nextarc!=NULL {
p=p->nextarc;
return p->adjvex; }
if(p->adjvex==w&&p->nextarc==NULL return -10; }

//**********************最小生成树PRIM算法******************* typedef struct {
int adjvex; int lowcost;
9

}closedge;
int prim(int g[][max],int n //最小生成树PRIM算法 {
int lowcost[max],prevex[max]; //LOWCOST[]存储当前集合U分别到剩余结点的最短路径
//prevex[]存储最短路径在U中的结点 int i,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集合 for(i=2;i<=n;i++ //形成n-1条边的生成树 {
min=inf; k=0;
for(j=2;j<=n;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 for(j=2;j<=n;j++ //修改由顶点k到其他顶点边的权值 if(g[k][j]<lowcost[j] {
lowcost[j]=g[k][j]; prevex[j]=k; }
printf("\n"; }
return 0; }
//**************************************************************
//**********************最小生成树kruscal算法******************* int acrvisited[100];//kruscal弧标记数组 int find(int acrvisited[],int f {
while(acrvisited[f]>0 f=acrvisited[f]; return f;
10

}
void kruscal_arc(MGraph_L G,algraph gra {
edg edgs[20]; int i,j,k=0;
for(i=0;i!=G.vexnum;++i for(j=i;j!=G.vexnum;++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; } }
int x,y,m,n; int buf,edf;
for(i=0;i!=gra.arcnum;++i acrvisited[i]=0;
for(j=0;j!=G.arcnum;++j {
m=10000;
for(i=0;i!=G.arcnum;++i {
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; cout<<endl; } }

11
}
//**************************************************************
//*********************主函数*********************************** int main( {
algraph gra; MGraph_L G;
int i,d,g[20][20]; char a='a';
d=creatMGraph_L(G; creatadj(gra,G; vnode v;

cout<<"*************菜单*************"<<endl<<endl;cout<<"0、最小生成树PRIM算法"<<endl;
cout<<"1、最小生成树KRUSCAL算法"<<endl<<endl; int s;
char y='y'; while(y='y' {
cout<<"请选择菜单："<<endl; cin>>s; switch(s {
case 0:
for(i=0;i!=G.vexnum;++i
for(int j=0;j!=G.vexnum;++j g[i+1][j+1]=G.arcs[i][j].adj; cout<<"prim:"<<endl; prim(g,d; break; case 1:
cout<<"kruscal:"<<endl; kruscal_arc(G,gra; break; }
cout<<endl<<"输入y返回菜单，输入n退出菜单y/n:"; cin>>y; if(y=='n' break; }
system("pause"; return 0;

12
}
//**************************************************************
四、输出结果


13

Kruskal算法结果

Prim算法


14

本文来源：https://www.2haoxitong.net/k/doc/7ba290bd0066f5335b812109.html

《西安电子科技大学离散数学大作业-.doc》
将本文的Word文档下载到电脑，方便收藏和打印
推荐度：
点击下载文档

文档为doc格式
相
关
案
例

相关推荐

推荐内容

大学军训内容- 大学新生军训感想的内容- 大学军训总结- 大学军训内容及项目- 大学军训心得体会集锦10篇- 大学军训日记- 大学军训心得体会集锦七篇- 大学军训日记范文八篇- 大学军训心得体会汇总9篇- 经济统计学发展前景和就业探讨
网站内容来自网络，如有侵权请联系我们，立即删除！ Copyright © 范文写作网京ICP备16605803号