克鲁斯卡尔算法
最近数据结构老师讲了好几个算法，今晚上正好有空，所以就来整理一下
一：Kruskal算法思想：直接以边为目标去构建最小生成树，注意只找出n-1条边即可，并且不能形成回路。图的存储结构采用的是边集数组，且权值相等的边在数组中的排练次序是任意的，如果图中的边数较多则此算法会很浪费时间！
二：Prim算法思想：以某一顶点为起点，一点一点的去找各顶点上最小权值的边来构建最小生成树。图的存储结构是邻接矩阵，此方法需要一个顶点集合T，开始的时候为空集，慢慢的会将连通的顶点陆续的加入到集合中，全部顶点都加入集合以后，就得到我们所需要的最小生成树啦！
#include "stdio.h"
#include "stdlib.h"
struct edge
{
int m;
int n;
int d;
}a[5010]; //克鲁斯卡尔算法采用边集数组来存储图
int cmp(const void *a,const void *b) //按升序排列，此过程也可以用快排来实现！
{
return ((struct edge *)a)->d>((struct edge *)b)->d;
}
int main(void)
{
int i,n,t,num,min,k,g,x[100];
printf("请输入顶点的个数：");
scanf("%d",&n);
t=n*(n-1)/2; //n个顶点的无向连通图共有n*(n-1)/2条边
for(i=1;i<=n;i++)
x[i]=i;
printf("请输入每条边的起始端点、权值：/n");
for(i=0;i<t;i++)
scanf("%d %d %d",&a[i].m,&a[i].n,&a[i].d); //输入每条边的权值
qsort(a,t,sizeof(a[0]),cmp);//此过程可以用快排，来将每条边权值从小到大排列起来
min=num=0;
for(i=0;i<t && num<n-1;i++)
{
for(k=a[i].m;x[k]!=k;k=x[k]) //判断线段的起始点所在的集合
x[k]=x[x[k]];
for(g=a[i].n;x[g]!=g;g=x[g]) //判断线段的终点所在的集合
x[g]=x[x[g]];
if(k!=g) //如果线段的两个端点所在的集合不一样
{
x[g]=k;
min+=a[i].d;
num++;
printf("最小生成树中加入边：%d %d/n",a[i].m,a[i].n);
}
}
printf("最小生成树的权值为：%d/n",min);
system("pause");
return 0;
}
克鲁斯卡尔算法代码实现方法二：
typedef struct
{
char vertex[VertexNum]; //顶点表
int edges[VertexNum][VertexNum]; //邻接矩阵,可看做边表
int n,e; //图中当前的顶点数和边数
}MGraph;
typedef struct node
{
int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
}Edge;
void kruskal(MGraph G)
{
int i,j,u1,v1,sn1,sn2,k;
int vset[VertexNum]; //辅助数组，判定两个顶点是否连通
int E[EdgeNum]; //存放所有的边
k=0; //E数组的下标从0开始
for (i=0;i<G.n;i++)
{
for (j=0;j<G.n;j++)
{
if (G.edges[i][j]!=0 && G.edges[i][j]!=INF)
{
E[k].u=i;
E[k].v=j;
E[k].w=G.edges[i][j];
k++;
}
}
}
heapsort(E,k,sizeof(E[0])); //堆排序，按权值从小到大排列
for (i=0;i<G.n;i++) //初始化辅助数组
{
vset[i]=i;
}
k=1; //生成的边数，最后要刚好为总边数
j=0; //E中的下标
while (k<G.n)
{
sn1=vset[E[j].u];
sn2=vset[E[j].v]; //得到两顶点属于的集合编号
if (sn1!=sn2) //不在同一集合编号内的话，把边加入最小生成树
{
printf("%d ---> %d, %d",E[j].u,E[j].v,E[j].w);
k++;
for (i=0;i<G.n;i++)
{
if (vset[i]==sn2)
{
vset[i]=sn1;
}
}
}
j++;
}
}
四：Prim算法具体实现
#define MAX 100000
#define VNUM 10+1 //这里没有ID为0的点,so id号范围1~10
int edge[VNUM][VNUM]={/*输入的邻接矩阵*/};
int lowcost[VNUM]={0}; //记录Vnew中每个点到V中邻接点的最短边
int addvnew[VNUM]; //标记某点是否加入Vnew
int adjecent[VNUM]={0}; //记录V中与Vnew最邻近的点
void prim(int start)
{
int sumweight=0;
int i,j,k=0;
for(i=1;i<VNUM;i++) //顶点是从1开始
{
lowcost[i]=edge[start][i];
addvnew[i]=-1; //将所有点至于Vnew之外,V之内，这里只要对应的为-1，就表示在Vnew之外
}
addvnew[start]=0; //将起始点start加入Vnew
adjecent[start]=start;
for(i=1;i<VNUM-1;i++)
{
int min=MAX;
int v=-1;
for(j=1;j<VNUM;j++)
{
if(addvnew[j]!=-1&&lowcost[j]<min) //在Vnew之外寻找最短路径
{
min=lowcost[j];
v=j;
}
}
if(v!=-1)
{
printf("%d %d %d\n",adjecent[v],v,lowcost[v]);
addvnew[v]=0; //将v加Vnew中
sumweight+=lowcost[v]; //计算路径长度之和
for(j=1;j<VNUM;j++)
{
if(addvnew[j]==-1&&edge[v][j]<lowcost[j])
{
lowcost[j]=edge[v][j]; //此时v点加入Vnew 需要更新lowcost
adjecent[j]=v;
}
}
}
}
printf("the minmum weight is %d",sumweight);
}
五：如果大家觉得这篇博客有问题，欢迎提意见，博主会认真学习哒~
文章最后发布于: 2018-11-28 20:22:07
相关阅读
文章主要与大家分享一些关于产品职业生涯中的一些底层认知，希望对你有所帮助~之前的两篇文章《基于Axure的移动端APP产品设计规范
朴素贝叶斯是基于“特征之间是独立的”这一朴素假设，应用贝叶斯定理的监督学习算法。基于条件概率的贝叶斯定律数学公式朴素贝叶斯
下面给你它们四则运算的规律：1奇函数+奇函数=奇函数2奇函数+偶函数=非奇非偶函数（特殊的可能是别的结果,不过特殊时可以用定义判断
刚接触数据结构，对于其中的一些算法都不是很了解，这几天刚在学习串的内容，里面介绍了两种串的模式匹配算法，一种是BF算法（也叫做BoyFri
A5创业网(admin5.com)9月14日消息，百度站长平台今日发布一则消息称，为保证用户搜索体验、促进搜索生态的良性发展，百度搜索将于9月底