前面我們談到的圖的數(shù)據(jù)結(jié)構(gòu)、圖的創(chuàng)建，今天我們就來說一說如何在圖中添加和刪除邊。邊的添加和刪除并不復(fù)雜，但是關(guān)鍵有一點(diǎn)需要記住，那就是一定要在小函數(shù)的基礎(chǔ)之上構(gòu)建大函數(shù)，否則很容易出現(xiàn)錯誤。

一、邊的創(chuàng)建

邊的創(chuàng)建一般來說可以分為下面以下幾個步驟：

1）判斷當(dāng)前圖中是否有節(jié)點(diǎn)，如果沒有，那么在pGraph->head處添加一條邊即可

2）如果當(dāng)前圖中有節(jié)點(diǎn)，那么判斷節(jié)點(diǎn)中有沒有以start點(diǎn)開頭的，如果沒有創(chuàng)建一個頂點(diǎn)和邊，并插入圖的head處

3）在當(dāng)前有節(jié)點(diǎn)start中，判斷是否end的邊已經(jīng)存在。如果end邊存在，返回出錯；否則在pVectex->neighbour處添加一條邊

4）添加的過程中注意點(diǎn)的個數(shù)和邊的個數(shù)處理

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;
}

二、邊的刪除

在進(jìn)行邊的刪除之前，我們需要對鏈表子節(jié)點(diǎn)進(jìn)行處理，構(gòu)建delete小函數(shù)，這樣可以在邊刪除函數(shù)中使用。

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）判斷圖中是否有節(jié)點(diǎn)存在，如果沒有，返回出錯

2）判斷圖中節(jié)點(diǎn)start是否存在，如果不存在，返回出錯

3）判斷節(jié)點(diǎn)start中是否end邊存在，如果不存在，返回出錯

4）刪除對應(yīng)的邊

5）判斷該節(jié)點(diǎn)的邊計數(shù)number是否為0，如果為0，繼續(xù)刪除節(jié)點(diǎn)

6）刪除過程中注意邊和頂點(diǎn)的個數(shù)處理

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;
}

注意事項(xiàng)：

（1）注意寫小函數(shù)，再復(fù)雜的功能都是有無數(shù)的小功能構(gòu)建的，函數(shù)最好不要超過50行

（2）老規(guī)矩，代碼務(wù)必要測試