#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_NAME 5
#define MAX_VERTEX_NUM 20
typedef char Vertex[MAX_NAME];/*顶点名字串*/
typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/
struct MGraph/*定义图*/
{
Vertex vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
};
typedef struct
{
Vertex adjvex; /*当前点*/
int lowcost; /*代价*/
}minside[MAX_VERTEX_NUM];
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,MAX_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; /*对称*/
}
}
void kruskal(MGraph G)
{
int set[MAX_VERTEX_NUM],i,j;
int k=0,a=0,b=0,min=G.arcs[a][b];
for(i=0;i<G.vexnum;i++)
set[i]=i;
printf("最小代价生成树的各条边为:\n");
while(k<G.vexnum-1)
{
for(i=0;i<G.vexnum;++i)
for(j=i+1;j<G.vexnum;++j)
if(G.arcs[i][j]<min)
{
min=G.arcs[i][j];
a=i;
b=j;
}
min=G.arcs[a][b]=0x7fffffff;
if(set[a]!=set[b])
{
printf("%s-%s\n",G.vexs[a],G.vexs[b]);
k++;
for(i=0;i<G.vexnum;i++)
if(set[i]==set[b])
set[i]=set[a];
}
}
}
int main()
{
MGraph g;
CreateGraph(g);
kruskal(g);
system("PAUSE");
return 0;
}
没有合适的资源?快使用搜索试试~ 我知道了~
资源详情
资源评论
资源推荐
收起资源包目录
最小生成树.rar (1个子文件)
smalltree.txt 3KB
共 1 条
- 1
qisblxy
- 粉丝: 1
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0