【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
前面我們談到的圖的數據結構、圖的創建，今天我們就來說一說如何在圖中添加和刪除邊。邊的添加和刪除並不復雜，但是關鍵有一點需要記住，那就是一定要在小函數的基礎之上構建大函數，否則很容易出現錯誤。
（a）邊的創建
邊的創建一般來說可以分為下面以下幾個步驟：
1）判斷當前圖中是否有節點，如果沒有，那麼在pGraph->head處添加一條邊即可
2）如果當前圖中有節點，那麼判斷節點中有沒有以start點開頭的，如果沒有創建一個頂點和邊，並插入圖的head處
3）在當前有節點start中，判斷是否end的邊已經存在。如果end邊存在，返回出錯；否則在pVectex->neighbour處添加一條邊
4）添加的過程中注意點的個數和邊的個數處理
view plaincopy to clipboardprint?STATUS insert_vectex_into_graph(GRAPH* pGraph, int start, int end, int weight)
{
VECTEX* pVectex;
LINE* pLine;
if(NULL == pGraph)
return FALSE;
if(NULL == pGraph->head){
pGraph->head = create_new_vectex_for_graph(start, end, weight);
pGraph->head->number ++;
pGraph->count ++;
return TRUE;
}
pVectex = find_vectex_in_graph(pGraph->head, start);
if(NULL == pVectex){
pVectex = create_new_vectex_for_graph(start, end, weight);
pVectex->next = pGraph->head;
pGraph->head = pVectex;
pGraph->head->number ++;
pGraph->count ++;
return TRUE;
}
pLine = find_line_in_graph(pVectex->neighbor, end);
if(NULL != pLine)
return FALSE;
pLine = create_new_line(end, weight);
pLine->next = pVectex->neighbor;
pVectex->neighbor = pLine;
pVectex->number ++;
return TRUE;
}
STATUS insert_vectex_into_graph(GRAPH* pGraph, int start, int end, int weight)
{
VECTEX* pVectex;
LINE* pLine;
if(NULL == pGraph)
return FALSE;
if(NULL == pGraph->head){
pGraph->head = create_new_vectex_for_graph(start, end, weight);
pGraph->head->number ++;
pGraph->count ++;
return TRUE;
}
pVectex = find_vectex_in_graph(pGraph->head, start);
if(NULL == pVectex){
pVectex = create_new_vectex_for_graph(start, end, weight);
pVectex->next = pGraph->head;
pGraph->head = pVectex;
pGraph->head->number ++;
pGraph->count ++;
return TRUE;
}
pLine = find_line_in_graph(pVectex->neighbor, end);
if(NULL != pLine)
return FALSE;
pLine = create_new_line(end, weight);
pLine->next = pVectex->neighbor;
pVectex->neighbor = pLine;
pVectex->number ++;
return TRUE;
}
（b）邊的刪除
在進行邊的刪除之前，我們需要對鏈表子節點進行處理，構建delete小函數，這樣可以在邊刪除函數中使用。
view plaincopy to clipboardprint?STATUS delete_old_vectex(VECTEX** ppVectex, int start)
{
VECTEX* pVectex;
VECTEX* prev;
if(NULL == ppVectex || NULL == *ppVectex)
return FALSE;
pVectex = find_vectex_in_graph(*ppVectex, start);
if(NULL == pVectex)
return FALSE;
if(pVectex == *ppVectex){
*ppVectex = pVectex->next;
free(pVectex);
return TRUE;
}
prev = *ppVectex;
while(pVectex != prev->next)
prev = prev->next;
prev->next = pVectex->next;
free(pVectex);
return TRUE;
}
STATUS delete_old_line(LINE** ppLine, int end)
{
LINE* pLine;
LINE* prev;
if(NULL == ppLine || NULL == *ppLine)
return FALSE;
pLine = find_line_in_graph(*ppLine, end);
if(NULL == pLine)
return FALSE;
if(pLine == *ppLine){
*ppLine = pLine->next;
free(pLine);
return TRUE;
}
prev = *ppLine;
while(pLine != prev->next)
prev = prev->next;
prev->next = pLine->next;
free(pLine);
return TRUE;
}
STATUS delete_old_vectex(VECTEX** ppVectex, int start)
{
VECTEX* pVectex;
VECTEX* prev;
if(NULL == ppVectex || NULL == *ppVectex)
return FALSE;
pVectex = find_vectex_in_graph(*ppVectex, start);
if(NULL == pVectex)
return FALSE;
if(pVectex == *ppVectex){
*ppVectex = pVectex->next;
free(pVectex);
return TRUE;
}
prev = *ppVectex;
while(pVectex != prev->next)
prev = prev->next;
prev->next = pVectex->next;
free(pVectex);
return TRUE;
}
STATUS delete_old_line(LINE** ppLine, int end)
{
LINE* pLine;
LINE* prev;
if(NULL == ppLine || NULL == *ppLine)
return FALSE;
pLine = find_line_in_graph(*ppLine, end);
if(NULL == pLine)
return FALSE;
if(pLine == *ppLine){
*ppLine = pLine->next;
free(pLine);
return TRUE;
}
prev = *ppLine;
while(pLine != prev->next)
prev = prev->next;
prev->next = pLine->next;
free(pLine);
return TRUE;
}
一般來說，邊的刪除和邊的添加是可逆的，過程如下所示：
1）判斷圖中是否有節點存在，如果沒有，返回出錯
2）判斷圖中節點start是否存在，如果不存在，返回出錯
3）判斷節點start中是否end邊存在，如果不存在，返回出錯
4）刪除對應的邊
5）判斷該節點的邊計數number是否為0，如果為0，繼續刪除節點
6）刪除過程中注意邊和頂點的個數處理
view plaincopy to clipboardprint?STATUS delete_vectex_from_graph(GRAPH* pGraph, int start, int end, int weight)
{
VECTEX* pVectex;
LINE* pLine;
STATUS result;
if(NULL == pGraph || NULL == pGraph->head)
return FALSE;
pVectex = find_vectex_in_graph(pGraph->head, start);
if(NULL == pVectex)
return FALSE;
pLine = find_line_in_graph(pVectex->neighbor, end);
if(NULL != pLine)
return FALSE;
result = delete_old_line(&pVectex->neighbor, end);
assert(TRUE == result);
pVectex->number --;
if(0 == pVectex->number)
result = delete_old_vectex(&pGraph->head, start);
assert(TRUE == result);
pGraph->count --;
return TRUE;
}
STATUS delete_vectex_from_graph(GRAPH* pGraph, int start, int end, int weight)
{
VECTEX* pVectex;
LINE* pLine;
STATUS result;
if(NULL == pGraph || NULL == pGraph->head)
return FALSE;
pVectex = find_vectex_in_graph(pGraph->head, start);
if(NULL == pVectex)
return FALSE;
pLine = find_line_in_graph(pVectex->neighbor, end);
if(NULL != pLine)
return FALSE;
result = delete_old_line(&pVectex->neighbor, end);
assert(TRUE == result);
pVectex->number --;
if(0 == pVectex->number)
result = delete_old_vectex(&pGraph->head, start);
assert(TRUE == result);
pGraph->count --;
return TRUE;
}
注意事項：
（1）注意寫小函數，再復雜的功能都是有無數的小功能構建的，函數最好不要超過50行
（2）老規矩，代碼務必要測試
