【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
克魯斯卡爾算法是計算最小生成樹的一種算法。和prim算法（上，中，下）按照節點進行查找的方法不一樣，克魯斯卡爾算法是按照具體的線段進行的。現在我們假設一個圖有m個節點，n條邊。首先，我們需要把m個節點看成m個獨立的生成樹，並且把n條邊按照從小到大的數據進行排列。在n條邊中，我們依次取出其中的每一條邊，如果發現邊的兩個節點分別位於兩棵樹上，那麼把兩棵樹合並成為一顆樹；如果樹的兩個節點位於同一棵樹上，那麼忽略這條邊，繼續運行。等到所有的邊都遍歷結束之後，如果所有的生成樹可以合並成一條生成樹，那麼它就是我們需要尋找的最小生成樹，反之則沒有最小生成樹。
上面的算法可能聽上去有些費解，我們可以用一個示例說明一下，
?/*
* 9
* D -----------
* 3 | |
* | 6 |
* A ------- B
* | |
* | 7 | 5
* -------C----
**/
/*
* 9
* D -----------
* 3 | |
* | 6 |
* A ------- B
* | |
* | 7 | 5
* -------C----
**/ 現在有這麼4個點。其中A-D 為3，A-C為7，A-B為6，B-D為9，B-C為5，下面就開始計算，我們首先默認所有的點都是單獨的最小生成樹，
copy to clipboardprint?/*
*
* D
*
* A B
*
* C
**/
/*
*
* D
*
* A B
*
* C
**/ 第一步，按照從小到大的順序，我們加入最小的邊A-D，
copy to clipboardprint?/*
*
* D
* 3 |
* |
* A B
*
*
* C
**/
/*
*
* D
* 3 |
* |
* A B
*
*
* C
**/ 然後，我們發現下面最小的邊是B-C，
copy to clipboardprint?/*
*
* D
* 3 |
* |
* A B
* |
* | 5
* C----
**/
/*
*
* D
* 3 |
* |
* A B
* |
* | 5
* C----
**/ 接著，我們發現最小的邊是A-B，因為點A和點B位於不同的最小生成樹上面，所以繼續合並，
copy to clipboardprint?/*
* D
* 3 |
* | 6
* A---------- B
* |
* | 5
* C----
**/
/*
* D
* 3 |
* | 6
* A---------- B
* |
* | 5
* C----
**/
接下來，我們還會遍歷A-C，B-D，但是我們發現此時邊的節點都已經遍歷過了，所以均忽略，最小生成樹的結構就是上面的內容。
那麼最小生成樹的數據結構是什麼，應該怎麼定義，不知道朋友們還記得否？我們曾經在prim算法中討論過，
copy to clipboardprint?/* 直連邊*/
typedef struct _DIR_LINE
{
int start;
int end;
int weight;
struct _DIR_LINE* next;
}DIR_LINE;
/* 最小生成樹*/
typedef struct _MINI_GENERATE_TREE
{
int node_num;
int line_num;
int* pNode;
DIR_LINE* pLine;
}MINI_GENERATE_TREE;
/* 節點邊信息*/
typedef struct _LINE
{
int end;
int weight;
struct _LINE* next;
}LINE;
/*節點信息*/
typedef struct _VECTEX
{
int start;
int number;
LINE* neighbor;
struct _VECTEX* next;
}VECTEX;
/* 圖信息*/
typedef struct _GRAPH
{
int count;
VECTEX* head;
}GRAPH;
/* 直連邊*/
typedef struct _DIR_LINE
{
int start;
int end;
int weight;
struct _DIR_LINE* next;
}DIR_LINE;
/* 最小生成樹*/
typedef struct _MINI_GENERATE_TREE
{
int node_num;
int line_num;
int* pNode;
DIR_LINE* pLine;
}MINI_GENERATE_TREE;
/* 節點邊信息*/
typedef struct _LINE
{
int end;
int weight;
struct _LINE* next;
}LINE;
/*節點信息*/
typedef struct _VECTEX
{
int start;
int number;
LINE* neighbor;
struct _VECTEX* next;
}VECTEX;
/* 圖信息*/
typedef struct _GRAPH
{
int count;
VECTEX* head;
}GRAPH;
