算法分析与设计---克鲁斯卡尔算法 - CSDN文库

克鲁斯卡尔算法

算法分析与设计

5星 · 超过95%的资源需积分: 15 65 浏览量更新于2023-03-16 评论 1 收藏 30KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

用 Kruskal 算法求解最小生成树问题：Kruskal 算法采用了最短边策略

(设 G=(V,E)是一个无向连通网，令 T=(U，TE)是 G 的最小生成树。最短边策略从

TE={}开始，每一次贪心选择都是在边集 E 中选择最短边(u,v)，如果边(u,v)加入集

合 TE 中不产生回路，则将边(u,v)加入边集 TE 中，并将它在集合 E 中删去。)，它

使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两

棵树合并，最后合并成一棵树。

Kruskal 算法实现代码如下：

#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/*定义图*/

{

6Vertex vexs[MAX_VERTEX_NUM];

6AdjMatrix arcs;

6int vexnum,arcnum;

}

typedef struct

{

6 Vertex adjvex; /*当前点*/

6 int lowcost;666 /*代价*/

}minside[MAX_VERTEX_NUM];

int LocateVex(MGraph G,Vertex u)//定位

{

6 int i;

6 for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)return i;

6 return -1;

}

void CreateGraph(MGraph &G)

{

6 int i,j,k,w;

6 Vertex va,vb;

6 printf("请输入无向网 G 的顶点数和边数(以空格为分隔)");

6 scanf("%d %d",&G.vexnum,&G.arcnum);

6 printf("请输入%d 个顶点的值(<%d 个字符):",G.vexnum,MAX_NAME);

6 for(i=0;i<G.vexnum;++i) /* 构造顶点集*/

666 scanf("%s",G.vexs[i]);

6 for(i=0;i<G.vexnum;++i) /*初始化邻接矩阵*/

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

评论7

yyf123yyfyya

2012-12-16

还可以，些的挺详细

il_joan

粉丝: 4
资源: 17

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈