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