kruskal算法c

A. 什么是Kruskal算法如何避圈

1. Kruskal算法
(1) 算法思想
K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
初始时没有任何边被选择。边（ 1 , 6）是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。下一步选择边（ 3，4）并将其加入树中（如图1 3 - 1 2 d所示）。然后考虑边( 2，7 ，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。下一步考虑边（ 2，3）并将其加入树中（如图1 3 - 1 2 f所示）。在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（ 5，4）加入树中，得到的树如图13-12g 所示。下一步考虑边（ 7，5），由于会产生环路，将其丢弃。最后考虑边（ 6，5）并将其加入树中，产生了一棵生成树，其耗费为9 9。图1 - 1 3给出了K r u s k a l算法的伪代码。

B. 用c语言写kruskal算法

既然思路你都懂，我就直接贴程序咯！

如下源代码来自CSDN大神分享

源代码仅网页端可见！

#include<stdio.h>
#defineMAXSIZE30
#defineMAXCOST32767

typedefstruct
{
	intu;//边的起始顶点
	intv;//边的起始终点
	intw;//边的权值
}Edge;

voidBubblesort(EdgeR[],inte)//冒泡排序，对数组R中的e条边按权值递增排序
{
	Edgetemp;
	inti,j,swap;
	for(i=0;i<e-1;j++)//进行e-1趟排序
	{
		swap=0;
		for(j=0;j<e-i-1;j++)
			if(R[j].w>R[j+1].w)
			{
				temp=R[j];R[j]=R[j+1];R[j+1]=temp;//交换R[j]和R[j+1]
				swap=1;//置有交换标志
			}
		if(swap==0)break;//本趟比较中未出现交换则结束排序
	}
}

voidKruskal(intgm[][6],intn)//在顶点为n的连接图中构造最小的生成树，gm为连通网的邻接矩阵
{
	inti,j,u1,v1,sn1,sn2,k;
	intvest[MAXSIZE];//数组vest用于判断两顶点之间是否连通
	EdgeE[MAXSIZE];//MAXSIZE为可存放边数的最大常量值
	k=0;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(i<j&&gm[i][j]!=MAXCOST)//MAXCOST为一个极大的常量值
			{
				E[k].u=i;
				E[k].v=j;
				E[k].w=gm[i][j];
				k++;
			}
	Bubblesort(E,k);//采用冒泡排序对数组E中的k条边按权值递增排序
	for(i=0;i<n;i++)//初始化辅助数组
		vest[i]=i;//给每个顶点置不同连通分量编号，即初始时有n个连通分量
	k=1;//k表示当前构造生成树的第n条边，初始值为1
	j=0;//j为数组E中元素的下标，初值为0
	while(k<n)//产生最小生成树的n-1条边
	{
		u1=E[j].u;v1=E[j].v;//取一条边的头尾顶点
		sn1=vest[u1];
		sn2=vest[v1];//分别得到这两个顶点所属的集合编号
		if(sn1!=sn2)//两顶点分属于不同集合则该边为最小生成树的一条边
		{
			printf("Edge:(%d,%d),Wight:%d
",u1,v1,E[j].w);
			k++;//生成的边数增1
			for(i=0;i<n;i++)//两个集合统一编号
				if(vest[i]==sn2)//集合编号为sn2的第i号边其边号改为sn1
					vest[i]=sn1;
		}
		j++;//扫描下一条边
	}
}
voidmain()
{
	intg[6][6]={{100,6,1,5,100,100},{6,100,5,100,3,100},{1,5,100,5,6,4},
	{5,100,5,100,100,2},{100,3,6,100,100,6},{100,100,4,2,6,100}};
	Kruskal(g,6);//生成最小生成树
	getchar();
}

运行如下图所示：

C. 哪位高手帮我写一个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;
}
}
}

D. kruskal算法实现 c代码

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

/* 定义边(x,y)，权为w */
typedef struct
{
int x, y;
int w;
}edge;

edge e[MAX];
/* rank[x]表示x的秩 */
int rank[MAX];
/* father[x]表示x的父节点 */
int father[MAX];
int sum;

/* 比较函数，按权值(相同则按x坐标)非降序排序 */
int cmp(const void *a, const void *b)
{
if ((*(edge *)a).w == (*(edge *)b).w)
{
return (*(edge *)a).x - (*(edge *)b).x;
}
return (*(edge *)a).w - (*(edge *)b).w;
}

/* 初始化集合 */
void Make_Set(int x)
{
father[x] = x;
rank[x] = 0;
}

/* 查找x元素所在的集合,回溯时压缩路径 */
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]);
}
return father[x];
}

/* 合并x,y所在的集合 */
void Union(int x, int y, int w)
{

if (x == y) return;
/* 将秩较小的树连接到秩较大的树后 */
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
sum += w;
}

/* 主函数 */
int main()
{
int i, n;
int x, y;
char chx, chy;

/* 读取边的数目 */
scanf("%d", &n);
getchar();

/* 读取边信息并初始化集合 */
for (i = 0; i < n; i++)
{
scanf("%c %c %d", &chx, &chy, &e[i].w);
getchar();
e[i].x = chx - 'A';
e[i].y = chy - 'A';
Make_Set(i);
}

/* 将边排序 */
qsort(e, n, sizeof(edge), cmp);

sum = 0;

for (i = 0; i < n; i++)
{
x = Find_Set(e[i].x);
y = Find_Set(e[i].y);
if (x != y)
{
printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w);
Union(x, y, e[i].w);
}
}

printf("Total:%d\n", sum);
//system("pause");
return 0;
}

E. c加加提问，克鲁斯卡尔算法是什么

克鲁斯卡尔算法，从边的角度求网的最小生成树，时间复杂度为O(eloge)。和普里姆算法恰恰相反，更适合于求边稀疏的网的最小生成树。

对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。

由于最小生成树本身是一棵生成树，所以需要时刻满足以下两点：

• 生成树中任意顶点之间有且仅有一条通路，也就是说，生成树中不能存在回路；

• 对于具有 n 个顶点的连通网，其生成树中只能有 n-1 条边，这 n-1 条边连通着 n 个顶点。

连接 n 个顶点在不产生回路的情况下，只需要 n-1 条边。

• 所以克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。



判断是否会产生回路的方法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。

• 假设遍历到一条由顶点 A 和 B 构成的边，而顶点 A 和顶点 B 标记不同，此时不仅需要将顶点 A 的标记更新为顶点 B 的标记，还需要更改所有和顶点 A 标记相同的顶点的标记，全部改为顶点 B 的标记。


（6）



• 当选取的边的数量相比与顶点的数量小 1 时，说明最小生成树已经生成。所以最终采用克鲁斯卡尔算法得到的最小生成树为（6）所示。



• 实现代码：#include "stdio.h"#include "stdlib.h"#define MAX_VERtEX_NUM 20#define VertexType inttypedef struct edge{VertexType initial;VertexType end;VertexType weight;}edge[MAX_VERtEX_NUM];//定义辅助数组typedef struct {VertexType value;//顶点数据int sign;//每个顶点所属的集合}assist[MAX_VERtEX_NUM];assist assists;//qsort排序函数中使用，使edges结构体中的边按照权值大小升序排序int cmp(const void *a,const void*b){return ((struct edge*)a)->weight-((struct edge*)b)->weight;}//初始化连通网void CreateUDN(edge *edges,int *vexnum,int *arcnum){printf("输入连通网的边数： ");scanf("%d %d",&(*vexnum),&(*arcnum));printf("输入连通网的顶点： ");for (int i=0; i<(*vexnum); i++) {scanf("%d",&(assists[i].value));assists[i].sign=i;}printf("输入各边的起始点和终点及权重： ");for (int i=0 ; i<(*arcnum); i++) {scanf("%d,%d,%d",&(*edges)[i].initial,&(*edges)[i].end,&(*edges)[i].weight);}}//在assists数组中找到顶点point对应的位置下标int Locatevex(int vexnum,int point){for (int i=0; i<vexnum; i++) {if (assists[i].value==point) {return i;}}return -1;}int main(){int arcnum,vexnum;edge edges;CreateUDN(&edges,&vexnum,&arcnum);//对连通网中的所有边进行升序排序，结果仍保存在edges数组中qsort(edges, arcnum, sizeof(edges[0]), cmp);//创建一个空的结构体数组，用于存放最小生成树edge minTree;//设置一个用于记录最小生成树中边的数量的常量int num=0;//遍历所有的边for (int i=0; i<arcnum; i++) {//找到边的起始顶点和结束顶点在数组assists中的位置int initial=Locatevex(vexnum, edges[i].initial);int end=Locatevex(vexnum, edges[i].end);//如果顶点位置存在且顶点的标记不同，说明不在一个集合中，不会产生回路if (initial!=-1&& end!=-1&&assists[initial].sign!=assists[end].sign) {//记录该边，作为最小生成树的组成部分minTree[num]=edges[i];//计数+1num++;//将新加入生成树的顶点标记全不更改为一样的for (int k=0; k<vexnum; k++) {if (assists[k].sign==assists[end].sign) {assists[k].sign=assists[initial].sign;}}//如果选择的边的数量和顶点数相差1，证明最小生成树已经形成，退出循环if (num==vexnum-1) {break;}}}//输出语句for (int i=0; i<vexnum-1; i++) {printf("%d,%d ",minTree[i].initial,minTree[i].end);}return 0;}


• 测试数据：



输入连通网的边数：
6 10
输入连通网的顶点：
1
2
3
4
5
6
输入各边的起始点和终点及权重：
1,2,6
1,3,1
1,4,5
2,3,5
2,5,3
3,4,5
3,5,6
3,6,4
4,6,2
5,6,6
1,3
4,6
2,5
3,6
2,3

F. 求kruskal算法的C语言标准程序 越简单越好！

给你个C++的，和C差不多，就头文件、文件读取不一样
#include<iostream>
#include<fstream>

using namespace std;

ifstream fin("data.in");
ofstream fout("data.out");

int v,e;
int L[1000]={0},R[1000]={0},W[1000]={0};
int f[100]={0};
int ans=0;

int find_set(int m)
{
if(m!=f[m]) f[m]=find_set(f[m]);
return f[m];
}

void Kruskal()
{
for(int i=1;i<=v; ++i)//初始化并查集
f[i]=i;

for(int i=1; i<=e; ++i)
{
int x,y;
x=find_set(L[i]); y=find_set(R[i]);
if(x!=y)
{
ans+=W[i];
f[y]=x;
}
}

fout<<ans;
}

void kp(int left,int right)
{
int i=left,j=right,mid=W[(left+right)>>1],t;
while(i<=j)
{
while(W[i]<mid) ++i;
while(W[j]>mid) --j;
if(i<=j)
{
t=L[i]; L[i]=L[j]; L[j]=t;
t=R[i]; R[i]=R[j]; R[j]=t;
t=W[i]; W[i]=W[j]; W[j]=t;
++i; --j;
}
}

if(i<right) kp(i,right);
if(left<j) kp(left,j);
}

int main()
{
fin>>v>>e;
for(int i=1; i<=e; ++i)
fin>>L[i]>>R[i]>>W[i];
kp(1,e);

Kruskal();

return 0;
}

G. 求kruskal算法的C语言程序 越简单越好a

对于c语言，指针是灵魂，特别是在稍微高级点的程序中，指针是必不可少的。以下程序没有用到链表，结构体用到了。当然如果你一定要用二维数组代替结构体去存储也行，代码会变得相当麻烦而且可读性差，维护困难。
另外注释加上了。代码临时写成，自带个人风格呵呵。

#include <stdio.h>
#include <stdlib.h>
#define TURE 1
#define FALSE 0
#define MAX 1000
#define abs(a) a > 0 ? a : -a
//图相关----------------------
typedef struct Tnode
{
int loc;
struct Tnode *next;
} Tnode; //顶点存放结点
typedef struct Ttable
{
Tnode *head;
Tnode *rear;
int length;
} Ttable; //顶点链表结构
typedef int ArcCell; /*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/
typedef int booleanType; //状态变量
typedef struct
{
ArcCell **arcs; /*邻接矩阵*/
int vexnum; /*图的顶点数和弧数*/
} MGraph; /*（Adjacency Matrix Graph）*/
//----------------------------
//队列相关（链式）-------------
typedef struct QNode //队列结点
{
int data;
struct QNode *next;
} QNode;

typedef struct //队列
{
QNode *front, *rear;
} LinkQueue;
//-----------------------------

MGraph G; //图
ArcCell **steparcs; //辅助矩阵
Ttable TE; //顶点链表指针
booleanType *visited; //建立标志数组(全局量）
LinkQueue Q; //定义队列

int GetGraph(MGraph *G); //建立图结构
void Back(); //还原矩阵
int kruskalTravel(MGraph G); //克鲁斯卡尔算法建立最小生成树
int MinSearch(MGraph G, int *i, int *j); //查找权值最小的边，以i，j返回其两端顶点。
int FirstAdjVex(int v);
int NextAdjVex(int v, int w);
int InitQueue(LinkQueue *Q); //初始化队列
int EmptyQueue(LinkQueue Q); //判空
int EnQueue(LinkQueue *Q, int v); //入队
int OutQueue(LinkQueue *Q); //出队
int WFSTravel(MGraph *G, LinkQueue *Q, int x, int y); //广度遍历含有i的连通分量，如果含有j顶点，返回TRUE，否则返回FALSE
int main()
{
GetGraph(&G);
printf("Kruskal:\n");
kruskalTravel(G);
return 0;
}

int GetGraph(MGraph *G) //建立邻接矩阵
{
int i, j;
scanf("%d", &(G->vexnum));
G->arcs = (ArcCell**)malloc(sizeof(ArcCell*) * G->vexnum);
for(i = 0; i < G->vexnum; i++)
{
G->arcs[i] = (ArcCell*)malloc(sizeof(ArcCell) * G->vexnum);
} //建立二维动态数组

for(i = 0; i < G->vexnum; i++)
{
for(j = 0; j < G->vexnum; j++)
{
scanf("%d", G->arcs[i] + j);
}
} //输入数据
return 0;
}//GetGraph

int kruskalTravel(MGraph G) //克鲁斯卡尔算法建立最小生成树
{
int i, j;
int N = G.vexnum;

steparcs = (ArcCell**)malloc(sizeof(ArcCell*) * G.vexnum); //建立二维动态数组
for(i = 0; i < G.vexnum; i++)
{
steparcs[i] = (ArcCell*)malloc(sizeof(ArcCell) * G.vexnum);
} //建立二维动态数组
for(i = 0; i < G.vexnum; i++) //初始化辅助矩阵
{
for(j = 0; j < G.vexnum; j++)
{
steparcs[i][j] = 0;
printf("%d ", steparcs[i][j]);
}
printf("\n");
}
printf("\n");

while(N > 1) //只要剩余的连通分量大于一，就继续链接各个连通分量
{
//查找权值最小的边，以i，j返回其两端顶点。如果两个顶点属于同一连通分量，则查找权次最小边，标志矩阵为负
MinSearch(G, &i, &j);
if(!WFSTravel(&G, &Q, i, j)) //广度遍历含有i的连通分量，如果含有j顶点，返回TRUE，否则返回FALSE
{
steparcs[i][j] = steparcs[j][i] = G.arcs[i][j]; //将符合条件的边和顶点并入到连通分量中
G.arcs[i][j] *= -1; //标志邻接矩阵，表明此条边已经查询过
G.arcs[j][i] *= -1;
N--; //剩余的连通分量
for(i = 0; i < G.vexnum; i++) //输出本次步骤
{
for(j = 0; j < G.vexnum; j++)
{
printf("%d ", steparcs[i][j]);
}
printf("\n");
}
printf("\n");
} //if
} //while

return 0;
}

int MinSearch(MGraph G, int *i, int *j) //查找权值最小的边，返回其值，并以i，j返回其两端顶点。
{
int temp = MAX; //存放当前最小值
int m, n;
for(n = 0; n < G.vexnum; n++) //循环查找
{
for(m = 0; m < G.vexnum; m++)
{
if(G.arcs[n][m] > 0 && G.arcs[n][m] < temp) //找最小值
{
temp = G.arcs[n][m];
*i = n;
*j = m;
}
}
}
return temp;
}

int FirstAdjVex(int v)
{
int i;

for(i = 0; i < G.vexnum; i++)
if(steparcs[v][i] != 0)
return i;
return -1;
}

// 返回下一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
int NextAdjVex(int v, int w)
{
int i;
for(i = w + 1; i < G.vexnum; i++)
if(steparcs[v][i] != 0)
return i;
return -1;
}

int InitQueue(LinkQueue *Q) //初始化队列
{
Q->front = Q->rear = (QNode*)malloc(sizeof(QNode)); //头结点
return 0;
}

int EmptyQueue(LinkQueue Q) //判空
{
return Q.front == Q.rear ? 1 : 0;
}

int EnQueue(LinkQueue *Q, int v) //入队
{
Q->rear->next = (QNode*)malloc(sizeof(QNode));
Q->rear = Q->rear->next;
Q->rear->data = v;
return 0;
}

int OutQueue(LinkQueue *Q) //出队
{
int e;
QNode *p;
if(Q->front == Q->rear)
{
printf("Queue Empty\n");
exit(0);
}
p = Q->front;
Q->front = Q->front->next;
e = Q->front->data;
free(p);
return e; //返回队头元素
}

//广度遍历含有i的连通分量，如果含有j顶点，返回TRUE，否则返回FALSE
int WFSTravel(MGraph *G, LinkQueue *Q, int x, int y)
{
int v, vtop = x, i;
visited = (booleanType*)malloc(sizeof(booleanType) * G->vexnum);
InitQueue(Q);
for(v = 0; v < G->vexnum; v++) //初始化标志数组
{
visited[v] = FALSE;
}

v = vtop; //初始查询顶点
if(!visited[v]) //如果没有遍历过，从此处开始遍历
{
visited[v] = TURE; //遍历该结点并标志结点状态
EnQueue(Q, v);
while(!EmptyQueue(*Q)) //如果队列中有元素，继续访问其邻接点
{
i = OutQueue(Q);
for(v = FirstAdjVex(i); v >= 0; v = NextAdjVex(i, v)) //寻找一个顶点的所有邻接点
{
if(!visited[v]) //访问未访问过的顶点
{
visited[v] = TURE;
if(v == y)
{
G->arcs[x][y] *= -1; //标志邻接矩阵，表明此条边已经查询过
G->arcs[y][x] *= -1;
return 1;
}
EnQueue(Q, v);
}
} //寻找一个顶点的所有邻接点
} //如果队列中有元素，继续访问其邻接点
} //如果没有遍历过，从此处开始遍历
return 0;
}//WFSprint

H. 求最小生成树 利用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)
不知是否满足您的要求

I. C语言 克鲁斯卡尔算法怎么判断是否构造成回路求大手解答

使用并查集，每个讲克鲁斯卡尔的算法都会涉及并查集。
初始为每个顶点属于互不相同的集合，当添加一条边时，就把这两条边的顶点加入到同一集合。如果边的两顶点属于不同集合，就可以添加这条边，否则就不可以添加（会构成回路）。
对于集合的操作，有子集的划分。前几天的天津还是哪个regional网络预赛，就有个子集划分的题目。

J. 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;
}