kruskal算法c语言

‘壹’ 求最小生成树的kruska算法，效率尽量高，尽量多点注释！c++代码

/*
基本算法思想：
为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。
具体作法如下：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。
由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选。

用并查积 和 克鲁是卡尔算法实现查找最短边
利用快排按边递增排列，每次从中选出最短边,同时将最短边的两个顶点并入到集合中
心得：利用并查积 和 kruskal算法结合找最短路径可以使查找的效率更高
加入集合中的边都是构成最小生成树的边，所以每家一次sum 都要加上这两个顶点之间的距离
*/
/*下面的代码输入n个节点，然后输入n*（n-1）/2条边及权值，输出是连通这些边的最小权值*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

struct ed
{
int u; //起始点
int v; //终结点
int w; //权重
};
bool cmp(ed a,ed b)
{
return a.w<b.w; //从小到大排序
}
struct ed edge[100000];
int p[105];

int find(int x) //查找x的父亲
{
while(p[x]!=x)
x=p[x];
return x;
}
int kruskal(int n)
{
int i,count=1,sum=0;
for(i=0;i<=n;i++)
p[i]=i; //并查集初始化，每个节点到父亲是自己
int x,y;
sort(edge,edge+n*(n-1)/2,cmp); //快速排序
for(i=0;count<n;i++)
{
x=find(edge[i].u); //点edge[i].u的父亲是x
y=find(edge[i].v); //点edge[i].v的父亲是y
if(x!=y) //判断是否会路
{
count++; //加上一条边
p[x]=y; //把x和y加入统一个集合
sum+=edge[i].w;
}
}
return sum;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n) //输入n个节点
{
int i;
for(i=0;i<n*(n-1)/2;i++) //输入 n*（n-1）/2条边
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); //表示点edge[i].u和点edge[i].v之间的权重为 edge[i].w
printf("%d\n",kruskal(n));
}
return 0;
}

楼主，这可是本人一个字一个字敲出来点，要给分啊

‘贰’ C语言数据结构 克鲁斯卡尔算法求无向网的最小生成树。

//要用到并查集判断回路，代码先给你吧，看不懂追问
#include<algorithm>
#include<stdio.h>
usingnamespacestd;
#defineMAXN1005//假设点数不超过1000
intn,m;
intfa[MAXN];
intid[MAXN];
structEdge{//边的数据结构
intfrom,to;
intlen;
};
Edgeedge[MAXN*MAXN];
boolcmp(Edgea,Edgeb){//边的比较函数
returna.len<b.len;
}
intfind(intx){//并查集，用于判断是否与已选择的边构成环
if(fa[x]==-1)
returnx;
else
returnfa[x]=find(fa[x]);
}
voidKruskal(intn){
memset(fa,-1,sizeof(fa));//初始化fa数组
intcnt=0;
for(inti=0;i<m;i++){
intu=edge[i].from;
intv=edge[i].to;
intt1=find(u);//找第一个点的起始点
intt2=find(v);//找第二个点的起始点
if(t1!=t2){//如果不相等，则不构成回路
fa[t1]=t2;
			id[cnt]=i;
cnt++;		
if(cnt==n-1)//当已选了n-1条边时，退出循环
break;
}
}
}
intmain()
{
	while(scanf("%d%d",&n,&m))
	{
		inta,b,c;
		for(inti=0;i<m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			edge[i].from=min(a,b);
			edge[i].to=max(a,b);
			edge[i].len=c;
		}
		sort(edge,edge+m,cmp);
		Kruskal(n);
		for(inti=0;i<n-1;i++)
		{
			intt=id[i];
			printf("%d%d%d
",edge[t].from,edge[t].to,edge[t].len);
		}
	}
	return0;
}

‘叁’ 求最小生成树 利用Kruskal算法求图G的一棵最小生成树T，用c语言

#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 并查集存储结返卖构
// Tags: 值为-1则表示为根节点
struct DisjointSet
{
int *arr;// 值为父节点下标
int number;// arr元素个数
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化并查集结构
// Input: number - 元素的个数
// Output:s - number个元素自成一集的并查集
void InitSet(DisjointSet &s, int number)
{
s.number = number;
s.arr = new int[number];
memset(s.arr, -1, sizeof(int) * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 删除并查集结构
// Input: s - 并查集存储结构
// Output:s - 回收内存后的结构
void FreeSet(DisjointSet &s)
{
if (s.arr)
{
delete []s.arr;
s.number = 0;
}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 获得某个结点的根节点
// Input: s - 并查集; index - 结点下标
// Output: return - 根节点下标
int GetRoot(DisjointSet &s, int index)
{
while (s.arr[index] != -1)
index = s.arr[index];

return index;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 合并index1和index2所在的两个集合
// Input: index1 - 结点1下标, index2 - 结点2下标
// Output: s - 并查集
void Union(DisjointSet &s, int index1, int index2)
{
int root1 = GetRoot(s, index1);
int root2 = GetRoot(s, index2);

s.arr[root1] = root2;
}

////////////////////////////////////////////////////////////////////////////////////////漏拆逗///////////////////////////////
// Description: 判断两个结点是否在同一个集合中
// Input: s - 并查集, index1 - 结点1下标, index2 - 结点2下标
// Output: return - true: 在 false: 不在
bool Find(DisjointSet &s, int index1, int index2)
{
return GetRoot(s, index1) == GetRoot(s, index2);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 图的邻接矩阵
struct Graph
{
int **value;// 权值,-1表示无法到达
int number;
};

/////////////御陪//////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化一个图
// Input: g - 图的存储结构, number - 结点个数
// Output: g - 图
void InitGraph(Graph &g, int number)
{
int i = 0;

g.value = new int *[number];
for (i = 0; i < number; i++)
g.value[i] = new int[number];

g.number = number;
memset(*g.value, -1, sizeof(int) * number * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 回收一个图
// Input: g - 图, number - 结点个数
// Output: g - 图的存储结构
void FreeGraph(Graph &g)
{
int i = 0;

for (i = 0; i < g.number; i++)
delete []g.value[i];

delete []g.value;

g.value = 0;
g.number = 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 为图在a，b间添加一条边
// Input:e1, e2 - 两个结点, value - 权值
// Output: graph - 加边后的图
void AddEdge(Graph &graph, int e1, int e2, int value)
{
graph.value[e1][e2] =value;
graph.value[e2][e1] = value;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 显示一条边
struct OneEdge
{
OneEdge(int _a = 0, int _b = 0, int _value = 0):
a(_a), b(_b), value(_value){}

int a, b;// 边的两个结点
int value; // 边的权值
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 根据权值判断两个边的大小
// Tags: 由于priority_queue是最大堆，所以这里小于号变成大于号，从而使priority_queue变成最小堆
bool operator <(OneEdge e1, OneEdge e2)
{
if (e1.value > e2.value) return true;
else return false;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用户输入图的边
// Input: n - 加边的个数
// Output: graph - 加边后的图
// Tags: Console下用户输入点对(a, b, v)
void InputEdge(Graph &graph, int n)
{
int i = 0, a, b, v;
for (i = 0; i < n; i++)
{
scanf("%d %d %d", &a, &b, &v);
AddEdge(graph, a, b, v);
}
}

int main()
{
const int NODE_NUMBER = 6;
const int EDGE_NUMBER = 9;

Graph graph;// 图
DisjointSet set;// 并查集
priority_queue<OneEdge> edge;// 2叉堆

InitGraph(graph, NODE_NUMBER);// 初始化图
InputEdge(graph, EDGE_NUMBER);
InitSet(set, NODE_NUMBER); // 初始化并查集

int i = 0, j = 0;// 初始化堆
for (i = 0; i < NODE_NUMBER; i++)
for (j = i; j < NODE_NUMBER; j++)
if (graph.value[i][j] > 0)
edge.push(OneEdge(i, j, graph.value[i][j]));

int min_pay = 0;// 最小耗费值
int add_num = 0;// 已经添加了几个边
OneEdge min_value_edge;// 当前权值最小边

while (add_num < NODE_NUMBER - 1)
{
min_value_edge = edge.top();
// 这里是因为了STL中2叉堆的结构中有一个缓冲区
// 需要将缓冲区中的每一个元素弹出来
if(min_value_edge.value > 0 && !Find(set, min_value_edge.a, min_value_edge.b))
{
Union(set, min_value_edge.a, min_value_edge.b);
min_pay += min_value_edge.value;
add_num++;
}
edge.pop();
}

printf("%d", min_pay);
return 0;
}

这个是c++语言的，最小权值存储在min_pay中，树存储在并查集set中，且在获取最小权值路径的时候用了STL中的2叉堆，算法复杂度为O(|V| * lgE)
不知是否满足您的要求

‘肆’ 哪位高手帮我写一个C语言的Prim和Kruskal算法，有主函数调用可以调试的

void Kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXE];
for (i=0;i<n;i++) vset[i]=i; //初始化辅助数组
k=1; //k表示当前构造最小生成树的第几条边,初值为1
j=0; //E中边的下标,初值为0
while (k<n) //生成的边数小于n时循环
{
m1=E[j].u;m2=E[j].v; //取一条边的头尾顶点
sn1=vset[m1];sn2=vset[m2]; //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属于不同的集合,该边是最小生成树的一条边
{
printf(" (%d,%d):%d\n",m1,m2,E[j].w);
k++; //生成边数增1
for (i=0;i<n;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++; //扫描下一条边
}
}
void prim(MGraph g,int v)
{
int lowcost[MAXV],min,n=g.vexnum;
int closest[MAXV],i,j,k;
for (i=0;i<n;i++) //给lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<n;i++) //找出n-1个顶点
{
min=INF;
for (j=0;j<n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf(" 边(%d,%d)权为:%d\n",closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<n;j++) //修改数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}