2021年西安电子科技大学离散数学大作业.doc

离散数学大作业

班级：021231
学号：02123120
姓名：

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

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

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

一、 最小生成树研究进展
最小生成树能够使用Kruskal算法和Prim算法。下面具体介绍这两种算法。
Kruskal算法
求加权连通图最小生成树算法。kruskal算法总共选择n- 1条边, （共n条边）所使用贪婪准则是: 从剩下边中选择一条不会产生环路含有最小花费边加入已选择边集合中。注意到所选择边若产生环路则不可能形成一棵生成树。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算法*******************
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;
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;
}
}
}
//**************************************************************
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;
}
printf("\n");
}
return 0;
}
//**************************************************************
三、 代码
#include<stdio.h>
#include <iostream>
#include <malloc.h>
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)
{
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;

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)
{
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;
}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;
}
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;
}
}
}
//**************************************************************

//*********************主函数***********************************
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;
}
//**************************************************************
四、 输出结果

Kruskal算法结果

Prim算法