离散大作业.doc

离散数学导论大作业
---------最小生成树

一 问题描述：
求下图的最小生成树
1
11
3
9
8
7
4
6
5
10
2

a
b
c
d
e
f

二，问题求解
用Kruskal算法求解上述问题
1. Kruskal的算法描述如下：
K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

2. 代码如下：
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#define name 5//。。。。。。。。。。。。。。。。。。。。。。。。。。顶点名占5个字符
#define vertexnum 40 //。。。。。。。。。。。。。。。。。。。顶点数目最多为40
typedef char Vertex[name];//。。。。。。。。。。。。。。。顶点名字串
typedef int AdjMatrix[vertexnum][vertexnum];//邻接距阵
struct MGraph//。。。。。。。。。。。。。。。。。。。。。。。。。。定义图的结构体类型
{
Vertex vexs[vertexnum];
AdjMatrix arcs;
int vexnum,arcnum;
};
typedef struct
{
Vertex adjvex;//。。。。。。。。。。。。。。。。。。。。。。。。当前点
int lowcost;//。。。。。。。。。。。。。。。。。。。。。。。。。。代价
}minside[vertexnum];
//声明函数原型
int LocateVex(MGraph G,Vertex u);
void CreateGraph(MGraph&G);
int minimum(minside SZ,MGraph G);
void MiniSpanTree_PRIM(MGraph G,Vertex u);
//主函数
int main()
{
MGraph g;
CreateGraph(g);
MiniSpanTree_PRIM(g,g.vexs[0]);
system("PAUSE");
return 0;
}

int LocateVex(MGraph G,Vertex u)//。。。。。。。。。。。结点的定位
{
int i;
for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)return i;
return-1;
}

void CreateGraph(MGraph&G)//。。。。。。。。。。。。。。。。。。建立无向图
{
int i,j,k,w;
Vertex va,vb;
printf("请输入无向图G的顶点数和边数(以空格为分隔)\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请输入%d个顶点的值(<%d个符):\n",G.vexnum,name);
for(i=0;i<G.vexnum;++i)//。。。。。。。。。。。。。。。构造图的顶点集合
scanf("%s",G.vexs[i]);
for(i=0;i<G.vexnum;++i)//。。。。。。。。。。。。。。。初始化邻接矩阵
for(j=0;j<G.vexnum;++j)
G.arcs[i][j]=0x7fffffff;
printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔):\n",G.arcnum);
for(k=0;k<G.arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w);
i=LocateVex(G,va);
j=LocateVex(G,vb);
G.arcs[i][j]=G.arcs[j][i]=w;//。。。。。。。无向图边对称
}
}
int minimum(minside SZ,MGraph G)
{
int i=0,j,k,min;
while(!SZ[i].lowcost)i++;
min=SZ[i].lowcost;
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0&&min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,Vertex u)
{
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j)
{
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j];
}
closedge[k].lowcost=0;
printf("最小代价生成树的各条边为:\n");
for(i=1;i<G.vexnum;++i)
{
k=minimum(closedge,G);
printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j]<closedge[j].lowcost)
{
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j];
}
}
}

3. 运行结果如下所示：