【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
前面我們討論過圖的基本結構是什麼樣的。它可以是矩陣類型的、數組類型的，當然也可以使指針類型的。當然，就我個人而言，比較習慣使用的結構還是鏈表指針類型的。本質上，一幅圖就是由很多節點構成的，每一個節點上面有很多的分支，僅此而已。為此，我們又對原來的結構做了小的改變：
typedef struct _LINE
{
int end;
int weight;
struct _LINE* next;
}LINE;
typedef struct _VECTEX
{
int start;
int number;
LINE* neighbor;
struct _VECTEX* next;
}VECTEX;
typedef struct _GRAPH
{
int count;
VECTEX* head;
}GRAPH;
typedef struct _LINE
{
int end;
int weight;
struct _LINE* next;
}LINE;
typedef struct _VECTEX
{
int start;
int number;
LINE* neighbor;
struct _VECTEX* next;
}VECTEX;
typedef struct _GRAPH
{
int count;
VECTEX* head;
}GRAPH; 為了創建圖，首先我們需要創建節點和創建邊。不妨從創建節點開始，
VECTEX* create_new_vectex(int start)
{
VECTEX* pVextex = (VECTEX*)malloc(sizeof(VECTEX));
assert(NULL != pVextex);
pVextex->start = start;
pVextex->number = 0;
pVextex->neighbor = NULL;;
pVextex->next = NULL;
return pVextex;
}
VECTEX* create_new_vectex(int start)
{
VECTEX* pVextex = (VECTEX*)malloc(sizeof(VECTEX));
assert(NULL != pVextex);
pVextex->start = start;
pVextex->number = 0;
pVextex->neighbor = NULL;;
pVextex->next = NULL;
return pVextex;
}
接著應該創建邊了，
LINE* create_new_line(int end, int weight)
{
LINE* pLine = (LINE*)malloc(sizeof(LINE));
assert(NULL != pLine);
pLine->end = end;
pLine->weight = weight;
pLine->next = NULL;
return pLine;
}
LINE* create_new_line(int end, int weight)
{
LINE* pLine = (LINE*)malloc(sizeof(LINE));
assert(NULL != pLine);
pLine->end = end;
pLine->weight = weight;
pLine->next = NULL;
return pLine;
} 有了上面的內容，那麼創建一個帶有邊的頂點就變得很簡單了，
VECTEX* create_new_vectex_for_graph(int start, int end, int weight)
{
VECTEX* pVectex = create_new_vectex(start);
assert(NULL != pVectex);
pVectex->neighbor = create_new_line(end, weight);
assert(NULL != pVectex->neighbor);
return pVectex;
}
VECTEX* create_new_vectex_for_graph(int start, int end, int weight)
{
VECTEX* pVectex = create_new_vectex(start);
assert(NULL != pVectex);
pVectex->neighbor = create_new_line(end, weight);
assert(NULL != pVectex->neighbor);
return pVectex;
} 那麼，怎麼它怎麼和graph相關呢？其實也不難。
GRAPH* create_new_graph(int start, int end, int weight)
{
GRAPH* pGraph = (GRAPH*)malloc(sizeof(GRAPH));
assert(NULL != pGraph);
pGraph->count = 1;
pGraph->head = create_new_vectex_for_graph(start, end, weight);
assert(NULL != pGraph->head);
return pGraph;
}
GRAPH* create_new_graph(int start, int end, int weight)
{
GRAPH* pGraph = (GRAPH*)malloc(sizeof(GRAPH));
assert(NULL != pGraph);
pGraph->count = 1;
pGraph->head = create_new_vectex_for_graph(start, end, weight);
assert(NULL != pGraph->head);
return pGraph;
} 有了圖，有了邊，那麼節點和邊的查找也不難了。
VECTEX* find_vectex_in_graph(VECTEX* pVectex, int start)
{
if(NULL == pVectex)
return NULL;
while(pVectex){
if(start == pVectex->start)
return pVectex;
pVectex = pVectex->next;
}
return NULL;
}
LINE* find_line_in_graph(LINE* pLine, int end)
{
if(NULL == pLine)
return NULL;
while(pLine){
if(end == pLine->end)
return pLine;
pLine = pLine->next;
}
return NULL;
}
VECTEX* find_vectex_in_graph(VECTEX* pVectex, int start)
{
if(NULL == pVectex)
return NULL;
while(pVectex){
if(start == pVectex->start)
return pVectex;
pVectex = pVectex->next;
}
return NULL;
}
LINE* find_line_in_graph(LINE* pLine, int end)
{
if(NULL == pLine)
return NULL;
while(pLine){
if(end == pLine->end)
return pLine;
pLine = pLine->next;
}
return NULL;
}
總結：
（1）圖就是多個鏈表的聚合
（2）想學好圖，最好把前面的鏈表和指針搞清楚、弄扎實
（3）盡量寫小函數，小函數構建大函數，方便閱讀和調試
