⑴ 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演算法的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;
}
⑶ 求一個學過數據結構（C語言版）的大神，有一個關於克魯斯卡爾演算法和普里姆演算法的問題！
克魯斯卡爾和prime演算法都是最小生成樹的貪心演算法，可以證明其擁有最優解結構。證明簡單的可以參考wiki，要嚴格證明請參考演算法導論和計算機程序設計的藝術中的相關內容。由於其相關論文比較久遠，我也不建議你去查了。
⑷ 怎麼用克魯斯卡爾演算法輸出全部最小生成樹,求代碼C語言
你只要按深度優先或按廣度優先遍歷這個圖，就可以得到你所說的樹了
⑸ C語言 克魯斯卡爾演算法怎麼判斷是否構造成迴路求大手解答
使用並查集，每個講克魯斯卡爾的演算法都會涉及並查集。
初始為每個頂點屬於互不相同的集合，當添加一條邊時，就把這兩條邊的頂點加入到同一集合。如果邊的兩頂點屬於不同集合，就可以添加這條邊，否則就不可以添加（會構成迴路）。
對於集合的操作，有子集的劃分。前幾天的天津還是哪個regional網路預賽，就有個子集劃分的題目。
⑹ 用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語言克魯斯卡爾求最小生成樹
你好 樓主。
很幸運的看到你的問題。
但是又很遺憾到現在還沒有人回答你的問題。也可能你現在已經在別的地方找到了答案，那就得恭喜你啦。
對於你的問題我愛莫能助！
可能是你問的問題有些專業了。或者別人沒有遇到或者接觸過你的問題，所以幫不了你。建議你去問題的相關論壇去求助，那裡的人通常比較多，也比較熱心，可能能快點幫你解決問題。
希望我的回答也能夠幫到你！
祝你好運。
快過年了，
最後祝您全家幸福健康快樂每一天！
⑻ 求最小生成樹 利用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語言，克魯斯卡爾演算法里的找尾有什麼作用
網路里網路一下。