克魯斯卡爾算法是計算最小生成樹的一種算法。和prim算法（上，中，下）按照節(jié)點進行查找的方法不一樣，克魯斯卡爾算法是按照具體的線段進行的?，F(xiàn)在我們假設(shè)一個圖有m個節(jié)點，n條邊。首先，我們需要把m個節(jié)點看成m個獨立的生成樹，并且把n條邊按照從小到大的數(shù)據(jù)進行排列。在n條邊中，我們依次取出其中的每一條邊，如果發(fā)現(xiàn)邊的兩個節(jié)點分別位于兩棵樹上，那么把兩棵樹合并成為一顆樹；如果樹的兩個節(jié)點位于同一棵樹上，那么忽略這條邊，繼續(xù)運行。等到所有的邊都遍歷結(jié)束之后，如果所有的生成樹可以合并成一條生成樹，那么它就是我們需要尋找的最小生成樹，反之則沒有最小生成樹。

上面的算法可能聽上去有些費解，我們可以用一個示例說明一下，

/*
*          9
*    D -----------
*  3 |           |
*    |      6    |
*    A  -------  B
*    |           |
*    |   7       | 5
*    -------C----
**/

現(xiàn)在有這么4個點。其中 A-D 為3， A-C為7，A-B為6，B-D為9，B-C為5，下面就開始計算，我們首先默認所有的點都是單獨的最小生成樹，

/*
*
*    D
*
*    A           B
*
*          C
**/

第一步，按照從小到大的順序，我們加入最小的邊A-D，

/*
*
*    D
*  3 |
*    |
*    A           B
*
*
*           C
**/

然后，我們發(fā)現(xiàn)下面最小的邊是B-C，

/*
*
*    D
*  3 |
*    |
*    A           B
*                |
*                | 5
*           C----
**/

接著，我們發(fā)現(xiàn)最小的邊是A-B，因為點A和點B位于不同的最小生成樹上面，所以繼續(xù)合并，

/*
*    D
*  3 |
*    |     6
*    A---------- B
*                |
*                | 5
*           C----
**/

接下來，我們還會遍歷A-C，B-D，但是我們發(fā)現(xiàn)此時邊的節(jié)點都已經(jīng)遍歷過了，所以均忽略，最小生成樹的結(jié)構(gòu)就是上面的內(nèi)容。

那么最小生成樹的數(shù)據(jù)結(jié)構(gòu)是什么，應(yīng)該怎么定義，不知道朋友們還記得否？我們曾經(jīng)在prim算法中討論過，

/* 直連邊 */
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;

/* 節(jié)點邊信息 */
typedef struct _LINE
{
    int end;
    int weight;
    struct _LINE* next;
}LINE;

/*節(jié)點信息*/
typedef struct _VECTEX
{
    int start;
    int number;
    LINE* neighbor;
    struct _VECTEX* next;
}VECTEX;

/* 圖信息 */
typedef struct _GRAPH
{
    int count;
    VECTEX* head;
}GRAPH;