【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
前面我們討論了圖的創建、添加、刪除和保存等問題。今天我們將繼續討論圖的一些其他問題，比如說如何在圖的環境下構建最小生成樹。為什麼要構建最小生成樹呢？其實原理很簡單。打個比方，現在某一個鄉鎮有n個村，那麼這n個村肯定是聯通的。現在我們打算在各個村之間搭建網線，實現村村通的工程。那麼有什麼辦法可以實現村村互通，同時又使得最後的總距離最小呢？要達到這個目的，就必須在已有的圖中構建最小生成樹。
生成最小生成樹的方法很多，prim方法就是其中的一種。那麼生成最小生成樹的基本步驟是什麼呢？很簡單，聽我慢慢道來：
1）以某一個點開始，尋找當前該點可以訪問的所有的邊；
2）在已經尋找的邊中發現最小邊，這個邊必須有一個點還沒有訪問過，將還沒有訪問的點加入我們的集合，記錄添加的邊；
3）尋找當前集合可以訪問的所有邊，重復2的過程，直到沒有新的點可以加入；
4）此時由所有邊構成的樹即為最小生成樹。
那麼，代碼應該怎麼編寫呢？朋友們可以自己好好思考一下。
a）首先，我們定義基本的數據結構。
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 _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的基本操作
view plaincopy to clipboardprint?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;
}
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;
}
