前面我們討論了圖的創(chuàng)建、添加、刪除和保存等問題。今天我們將繼續(xù)討論圖的一些其他問題，比如說如何在圖的環(huán)境下構(gòu)建最小生成樹。為什么要構(gòu)建最小生成樹呢？其實(shí)原理很簡單。打個(gè)比方，現(xiàn)在某一個(gè)鄉(xiāng)鎮(zhèn)有n個(gè)村，那么這n個(gè)村肯定是聯(lián)通的?，F(xiàn)在我們打算在各個(gè)村之間搭建網(wǎng)線，實(shí)現(xiàn)村村通的工程。那么有什么辦法可以實(shí)現(xiàn)村村互通，同時(shí)又使得最后的總距離最小呢？要達(dá)到這個(gè)目的，就必須在已有的圖中構(gòu)建最小生成樹。

生成最小生成樹的方法很多，prim方法就是其中的一種。那么生成最小生成樹的基本步驟是什么呢？很簡單，聽我慢慢道來：

1）以某一個(gè)點(diǎn)開始，尋找當(dāng)前該點(diǎn)可以訪問的所有的邊；

2）在已經(jīng)尋找的邊中發(fā)現(xiàn)最小邊，這個(gè)邊必須有一個(gè)點(diǎn)還沒有訪問過，將還沒有訪問的點(diǎn)加入我們的集合，記錄添加的邊；

3）尋找當(dāng)前集合可以訪問的所有邊，重復(fù)2的過程，直到?jīng)]有新的點(diǎn)可以加入；

4）此時(shí)由所有邊構(gòu)成的樹即為最小生成樹。

那么，代碼應(yīng)該怎么編寫呢？朋友們可以自己好好思考一下。

a）首先，我們定義基本的數(shù)據(jù)結(jié)構(gòu)。

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;

**b）DIR_LINE的基本操作**

STATUS insert_line_into_queue(DIR_LINE** ppLine, int start, int end, int weight)
{
    DIR_LINE* pLine;

    if(NULL == ppLine)
        return FALSE;

    if(NULL == *ppLine){
        *ppLine = create_new_dir_line(start, end, weight);
        return TRUE;
    }

    pLine = create_new_dir_line(start, end, weight);
    pLine->next = *ppLine;
    *ppLine = pLine;
    return TRUE;
}

STATUS delete_line_from_queue(DIR_LINE** ppLine, DIR_LINE* pLine)
{
    DIR_LINE* prev;

    if(NULL == ppLine || NULL == *ppLine || NULL == pLine)
        return FALSE;

    if(pLine == *ppLine){
        *ppLine = pLine->next;
        goto final;
    }

    prev = *ppLine;
    while(pLine != prev->next)
        prev = prev->next;
    prev->next = pLine->next;

final:
    free(pLine);
    return TRUE;
}