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

1、离散数学大作业班级：021231学号：02123120姓名：题目：编程实现赋权有向图的最小生成树摘要求解图的最小生成树有三种算法，分别为Prim算法、Kruskal算法和Boruvka算法。这三种算法都是贪心算法。所以本次实验分别使用Kruskal算法和Prim算法实现赋权有向图的最小生成树。Kruskal算法基本思想为：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。具体作法如下：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变

2、成一棵树为止，这棵树便是连通网的最小生成树。Prim算法基本思想是：首先选取图中任意一个顶点 v 作为生成树的根，之后继续往生成树中添加顶点 w，则在顶点 w 和顶点 v 之间必须有边，且该边上的权值应在所有和 v 相邻接的边中属最小。关键词： 邻接矩阵；邻接表；Kruskal算法；Prim算法；最小生成树一、最小生成树的研究进展最小生成树可以使用Kruskal算法和Prim算法。下面具体介绍这两种算法。Kruskal算法求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n条边）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合

3、中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。该算法的时间复杂度为O(elge);Kruskal算法的时间主要取决于边数,它较适合于稀疏图。Kruskal算法构造最小生成树的过程图解:Prim算法Prim算法可以说是所有MST算法中最简单的，比较适用于稠密图。以图中任意一个顶点S开始，选择与之相关连的边中权值最小的边加入到MST中，假设这条边的终点为T，则MST初始化为(S, T)，称之为“当前MST”

4、。接下来在剩余的边中选择与当前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的顶点

5、集，TE是T的边集。prim算法适合稠密图，其时间复杂度为O(n2)，其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。二、最小生成树的实现Kruskal算法关键部分的实现Kruskal算法的计算流程大致如下：1.将无向图的边按距离长短递增式排序，放到集合中2.遍历该集合，找出最短的边，加入到结果生成树的集合中3.如果结果生成树出现回路，则放弃这条边4.重新执行步骤2，直至所有顶点被遍历可以看出在每次遍历过程中采用了贪心算法Kruskal算法代码如下：/*最小生成树kruscal算法*int acrvisited100;/kruscal弧

6、标记数组int find(int acrvisited,int f)while(acrvisitedf0)f=acrvisitedf;return f;void kruscal_arc(MGraph_L G,algraph gra)edg edgs20;int i,j,k=0;for(i=0;i!=G.vexnum;+i)for(j=i;j!=G.vexnum;+j) if(G.arcsij.adj!=10000) edgsk.pre=i; edgsk.bak=j; edgsk.weight=G.arcsij.adj; +k; int x,y,m,n;int buf,edf;for(i=0;i

7、!=gra.arcnum;+i)acrvisitedi=0;for(j=0;j!=G.arcnum;+j)m=10000;for(i=0;i!=G.arcnum;+i) if(edgsi.weightm) m=edgsi.weight; x=edgsi.pre; y=edgsi.bak; n=i; buf=find(acrvisited,x); edf=find(acrvisited,y); edgsn.weight=10000; if(buf!=edf) acrvisitedbuf=edf; cout(x,y)m; coutendl; /*Prim算法关键部分的实现Prim算法的计算流程大致

8、如： （1）初始状态，TE为空，U=v0，v0V； （2）在所有uU，vV-U的边(u，v) E中找一条代价最小的边(u，v)并入TE，同时将v并入U；重复执行步骤（2）n-1次，直到U=V为止。Prim算法代码如下：/*最小生成树PRIM算法*typedef structint adjvex;int lowcost;closedge;int prim(int gmax,int n) /最小生成树PRIM算法int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径 /prevex存储最短路径在U中的结点int i,j,k,min;for(i=2

9、;i=n;i+) /n个顶点，n-1条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 lowcost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf;k=0;for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min);lowcostk=0; /顶点k加入Ufor(j=2;j=n;j+) /修改由顶点k到

10、其他顶点边的权值 if(gkjlowcostj) lowcostj=gkj; prevexj=k; printf(n);return 0;/*三、代码#include#include #include using namespace std;#define int_max 10000#define inf 9999#define max 20/*邻接矩阵定义*typedef struct ArcCellint adj;char *info;ArcCell,AdjMatrixmaxmax;typedef structchar vexsmax;AdjMatrix arcs;int vexnum,a

11、rcnum;MGraph_L;/*int localvex(MGraph_L G,char v)/返回V的位置int i=0;while(G.vexsi!=v)+i;return i;int creatMGraph_L(MGraph_L &G)/创建图用邻接矩阵表示char v1,v2;int i,j,w;cout请输入图的顶点和弧的个数:例如4 6 (4表示顶点的个数，5表示弧的个数)G.vexnumG.arcnum;for(i=0;i!=G.vexnum;+i)cout输入顶点iG.vexsi;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j) G

12、.arcsij.adj=int_max; G.=NULL;for(int k=0;k!=G.arcnum;+k) cout输入一条边依附的顶点和权:例如a b c (a,b表示顶点，c表示权)v1v2w;/输入一条边依附的两点及权值 i=localvex(G,v1);/确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w;cout图G邻接矩阵创建成功！adjvex=j; gra.verticesi.firstarc=arc; arc-nextarc=NULL; p=arc; +j; while(G

13、.arcsij.adj!=int_max&j!=G.vexnum) tem=(arcnode *)malloc(sizeof(arcnode); tem-adjvex=j; gra.verticesi.firstarc=tem; tem-nextarc=arc; arc=tem; +j; -j; else if(G.arcsij.adj!=int_max&j!=G.vexnum) arc=(arcnode *)malloc(sizeof(arcnode); arc-adjvex=j; p-nextarc=arc; arc-nextarc=NULL; p=arc; gra.vexnum=G.ve

14、xnum;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-n

15、extarc; return p-adjvex;if(p-adjvex=w&p-nextarc=NULL)return -10;/*最小生成树PRIM算法*typedef structint adjvex;int lowcost;closedge;int prim(int gmax,int n) /最小生成树PRIM算法int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径 /prevex存储最短路径在U中的结点int i,j,k,min;for(i=2;i=n;i+) /n个顶点，n-1条边 lowcosti=g1i; /初始化 preve

16、xi=1; /顶点未加入到最小生成树中 lowcost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf;k=0;for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min);lowcostk=0; /顶点k加入Ufor(j=2;j=n;j+) /修改由顶点k到其他顶点边的权值 if(gkj0)f=acrvisitedf;return f;void

17、kruscal_arc(MGraph_L G,algraph gra)edg edgs20;int i,j,k=0;for(i=0;i!=G.vexnum;+i)for(j=i;j!=G.vexnum;+j) if(G.arcsij.adj!=10000) edgsk.pre=i; edgsk.bak=j; edgsk.weight=G.arcsij.adj; +k; int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;+i)acrvisitedi=0;for(j=0;j!=G.arcnum;+j)m=10000;for(i=0;i!=G.arcnum;

18、+i) if(edgsi.weightm) m=edgsi.weight; x=edgsi.pre; y=edgsi.bak; n=i; buf=find(acrvisited,x); edf=find(acrvisited,y); edgsn.weight=10000; if(buf!=edf) acrvisitedbuf=edf; cout(x,y)m; coutendl; /*/*主函数*int main()algraph gra;MGraph_L G;int i,d,g2020;char a=a;d=creatMGraph_L(G);creatadj(gra,G);vnode v;cout*菜单*endlendl;cout0、最小生成树PRIM算法endl;cout1、最小生成树KRUSCAL算法endlen