前面我们谈到的图的数据结构、图的创建，今天我们就来说一说如何在图中添加和删除边。边的添加和删除并不复杂，但是关键有一点需要记住，那就是一定要在小函数的基础之上构建大函数，否则很容易出现错误。

一、边的创建

边的创建一般来说可以分为下面以下几个步骤：

1）判断当前图中是否有节点，如果没有，那么在pGraph->head处添加一条边即可

2）如果当前图中有节点，那么判断节点中有没有以start点开头的，如果没有创建一个顶点和边，并插入图的head处

3）在当前有节点start中，判断是否end的边已经存在。如果end边存在，返回出错；否则在pVectex->neighbour处添加一条边

4）添加的过程中注意点的个数和边的个数处理

view plaincopy to clipboardprint?

STATUS insert_vectex_into_graph(GRAPH* pGraph,intstart,intend,intweight) { VECTEX* pVectex; LINE* pLine;if(NULL==pGraph)returnFALSE;if(NULL==pGraph->head){ pGraph->head=create_new_vectex_for_graph(start, end, weight); pGraph->head->number ++; pGraph->count ++;returnTRUE; } 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 ++;returnTRUE; } pLine=find_line_in_graph(pVectex->neighbor, end);if(NULL !=pLine)returnFALSE; pLine=create_new_line(end, weight); pLine->next=pVectex->neighbor; pVectex->neighbor=pLine; pVectex->number ++;returnTRUE; }

二、边的删除

在进行边的删除之前，我们需要对链表子节点进行处理，构建delete小函数，这样可以在边删除函数中使用。

view plaincopy to clipboardprint?

STATUS delete_old_vectex(VECTEX** ppVectex,intstart) { VECTEX* pVectex; VECTEX* prev;if(NULL==ppVectex || NULL==*ppVectex)returnFALSE; pVectex=find_vectex_in_graph(*ppVectex, start);if(NULL==pVectex)returnFALSE;if(pVectex==*ppVectex){ *ppVectex=pVectex->next; free(pVectex);returnTRUE; } prev=*ppVectex;while(pVectex !=prev->next) prev=prev->next; prev->next=pVectex->next; free(pVectex);returnTRUE; } STATUS delete_old_line(LINE** ppLine,intend) { LINE* pLine; LINE* prev;if(NULL==ppLine || NULL==*ppLine)returnFALSE; pLine=find_line_in_graph(*ppLine, end);if(NULL==pLine)returnFALSE;if(pLine==*ppLine){ *ppLine=pLine->next; free(pLine);returnTRUE; } prev=*ppLine;while(pLine !=prev->next) prev=prev->next; prev->next=pLine->next; free(pLine);returnTRUE; }

一般来说，边的删除和边的添加是可逆的，过程如下所示：

1）判断图中是否有节点存在，如果没有，返回出错

2）判断图中节点start是否存在，如果不存在，返回出错

3）判断节点start中是否end边存在，如果不存在，返回出错

4）删除对应的边

5）判断该节点的边计数number是否为0，如果为0，继续删除节点

6）删除过程中注意边和顶点的个数处理

view plaincopy to clipboardprint?

STATUS delete_vectex_from_graph(GRAPH* pGraph,intstart,intend,intweight) { VECTEX* pVectex; LINE* pLine; STATUS result;if(NULL==pGraph || NULL==pGraph->head)returnFALSE; pVectex=find_vectex_in_graph(pGraph->head, start);if(NULL==pVectex)returnFALSE; pLine=find_line_in_graph(pVectex->neighbor, end);if(NULL !=pLine)returnFALSE; 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 --;returnTRUE; }

注意事项：

（1）注意写小函数，再复杂的功能都是有无数的小功能构建的，函数最好不要超过50行

（2）老规矩，代码务必要测试