kruskal演算法
對於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
② kruskal演算法的流程圖。
我也在找啊```~~~
③ 什麼是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演算法的偽代碼。
④ kruskal演算法的介紹
求加權連通圖的最小生成樹的演算法。kruskal演算法總共選擇n- 1條邊，（共n個點）所使用的貪婪准則是：從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。kruskal演算法分e 步，其中e 是網路中邊的數目。按耗費遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環路，則將其拋棄，否則，將它選入。
⑤ kruskal演算法是什麼
kruskal演算法是求加權連通圖的最小生成樹的演算法。
kruskal演算法總共選擇n- 1條邊，(共n個點)所使用的貪心准則是:從剩下的邊中選擇一條不會產生環路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環路則不可能形成一棵生成樹。
kruskal演算法分e步，其中e是網路中邊的數目。按耗費遞增的順序來考慮這e 條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環路，則將其拋棄，否則，將它選入。
Kruskal演算法基本思想：
每次選不屬於同一連通分量(保證不生成圈)且邊權值最小的頂點，將邊加入MST，並將所在的2個連通分量合並，直到只剩一個連通分量。
排序使用Quicksort(O(eloge))。
檢查是否在同一連通分量用Union-Find，每次Find和union運算近似常數。
Union-Find使用rank啟發式合並和路徑壓縮。
總復雜度O(eloge)=O(elogv) (因為e<n(n-1)/2)。
⑥ 求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;
}
⑦ kruskal演算法的舉例描述
克魯斯卡爾演算法(Kruskal's algorithm)是兩個經典的最小生成樹演算法的較為簡單理解的一個。這裡面充分體現了貪心演算法的精髓。大致的流程可以用一個圖來表示。這里的圖的選擇借用了Wikipedia上的那個。非常清晰且直觀。
首先第一步，我們有一張圖，有若干點和邊
第一步我們要做的事情就是將所有的邊的長度排序，用排序的結果作為我們選擇邊的依據。這里再次體現了貪心演算法的思想。資源排序，對局部最優的資源進行選擇。
排序完成後，我們率先選擇了邊AD。這樣我們的圖就變成了
.
.
.
.
.
.
第二步，在剩下的邊中尋找。我們找到了CE。這里邊的權重也是5
.
.
.
.
.
.
依次類推我們找到了6,7,7。完成之後，圖變成了這個樣子。
.
.
.
.
.
.
下一步就是關鍵了。下面選擇那條邊呢？ BC或者EF嗎？都不是，盡管現在長度為8的邊是最小的未選擇的邊。但是他們已經連通了（對於BC可以通過CE,EB來連接，類似的EF可以通過EB,BA,AD,DF來接連）。所以我們不需要選擇他們。類似的BD也已經連通了（這里上圖的連通線用紅色表示了）。
最後就剩下EG和FG了。當然我們選擇了EG。最後成功的圖就是下圖：
.
.
.
.
.
.
到這里所有的邊點都已經連通了，一個最小生成樹構建完成。
Kruskal演算法的時間復雜度由排序演算法決定，若採用快排則時間復雜度為O(N log N)。
⑧ Kruskal演算法適合於什麼圖
邊數較少可以用kruskal,因為kruskal演算法每次查找最短的邊。
邊數較多可以用prim，因為它是每次加一個頂點，對邊數多的適用。
⑨ kruskal演算法
給每個子樹一個不同的編號，對每一個頂點引入一個標記t，表示這個頂點所在的子樹編號。當加入一條紅色邊，就會使該邊兩端點所在的兩個子樹連接起來，成為一個子樹，從而兩個子樹中的頂點標記要改變成一樣。綜上，可將Kruskal演算法細化使其更容易計算機實現。
kruskal應該是遞歸演算法吧，在定義圖中各端點時，可以多設一個標記，把圖遞歸遍歷一遍，在同一連同子圖上的點，標記為一樣的整型數值即可。
參考：http://ke..com/view/580403.htm