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