圖是一種靈活的數據結構，它多用於描述對象之間的關係和連接模型。
關於圖的算法：最小生成樹、最短路徑、旅行商問題以及許多其他算法大都會使用到廣度優先搜索和深度優先搜索，因為它們提供了一套系統地訪問圖數據結構的方法。
帶權圖，是指圖的每條邊上帶有一個值或權，這些權用一個小的數字標記在邊上。很多條件因素都可以作為權值，但通常它表示遍歷這條邊所產生的代價。最小生成樹簡述我們做一個簡單的模型，在一塊木板上釘上一些釘子並用一些細繩連接起來，假設每一個釘子都經由一根或多根細繩連接起來。現在我們一根一根拿走細繩，直到用最少的細繩將所有釘子連接起來。這個模型的背後思想就是最小生成樹。
正式的表述法是，給定一個無方向的帶權圖G=（V，E），最小生成樹為集合T，T是以最小代價連接V中所有頂點所用邊E的最小集合。集合T中的邊能形成一顆樹，這是因為每個頂點都能向上找到它的一個父節點（根結點除外）。Prim算法Prim算法是一種產生最小生成樹的方法。Prim算法從任意一個頂點開始，每次選擇一個與當前頂點最近的一個頂點，並將兩個頂點之間的邊加入到樹中。從根本上講，Prim算法就是不斷的選擇頂點，並計算邊的權值，同時判斷是否還有更有效的連接方式。該算法類似廣度優先搜索算法，因為在往圖中更深的頂點探索之前，它首先要遍歷與此頂點相關的所有頂點。 每個階段都要決定選擇哪個頂點，所以 需要維護頂點的顏色和鍵值 。
開始，將所有頂點的色值設置為白色，鍵值設置為∞（它代表一個足夠大的數，大於圖中所有邊的權值）。同時，將起始頂點的鍵值設置為0。隨著算法的不斷演進，在最小生成樹中為每個頂點（除起始頂點外）指派一個父節點。只有當頂點的色值變為黑色時，此頂點才是最小生成樹的一部分。
Prim算法的運行過程如下：
首先，在圖中所有的白色頂點中，選擇鍵值最小的頂點u。開始，鍵值被設置為0的那一頂點將作為起始頂點。
當選擇此頂點之後，將其標記為黑色。
接下來，對於每個與u相鄰的頂點v，設置v的鍵值為邊（u，v）的權值，同時將u設置為v的父結點。
重複這個過程，直到所有的頂點都標記為黑色。
隨著最小生成樹的增長，該樹會包含圖中的所有的邊（連接所有頂點最少數量邊），且每條邊的兩端都有一個黑色的頂點。
下圖展示了最小生成樹的產生過程。在圖中，鍵值和父結點都顯示在每個頂點的旁邊，用斜線分開。鍵值顯示在斜線的左邊，父結點顯示在斜線的右邊。淺灰色的邊是最小生成樹增長過程中的邊。圖中最小生成樹總的權值為17。
最小生成樹的接口定義mstint mst(Graph *graph, const MstVertex *start, List *span, int (*match)(const void *key1, const void *key2));返回值：如果計算最小生成樹成功，返回0，否則返回-1。
描述：為一個 無方向的帶權圖 graph計算最小生成樹。
最小生成樹 從頂點start開始 。
此操作會改變graph，所以如果有必要，在調用此操作之前先對圖進行備份。
graph中的每個頂點必須包含MstVertex類型的數據。通過設置MstVertex結構體中的成員 weight的值來指定每個邊的權值 ， weight的值由傳入graph_ins_edge的參數data2決定 。用MstVertex結構體的成員data來保存與頂點相關的數據。
graph的match函數（此函數在用graph_init對圖進行初始化時調用）用來比較MstVertex結構體中的data成員。此函數與傳入mst中的參數match相同。
一旦計算完成，最小生成樹的相關數據將會返回到span。 span是存儲MstVertex結構體的列表 。在span中，父結點為NULL的頂點為最小生成樹的根結點。其他每個頂點的parent成員都指向span中位於該頂點之前的那個頂點。
span中的頂點指向graph中的實際頂點，所以只要能夠訪問span，函數調用者就必須保證graph中內存空間有效。一旦不再使用span，就調用list_destroy銷毀span。
複雜度：O（E V 2 ），其中V是圖中頂點的個數，E是邊的條數。
最小生成樹的實現與分析為了計算一個無方向的帶權圖的最小生成樹，首先，我們要用表示圖的基本抽象數據類型來表示帶權圖。同時，Prim算法還需要一種追蹤頂點和邊信息的方法。這就用到了MstVertex結構體：它用來為圖中的頂點計算最小生成樹。此結構包含5個成員：data是與頂點相關的數據；weight是到達該頂點的邊的權值；color是頂點的顏色；key是頂點的鍵值；parent是最小生成樹中頂點的父結點。
建立一個包含MstVertex結構體的圖的過程幾乎與建立一個包含其他類型的圖的過程一樣： 要將一個頂點插入圖中，調用graph_ins_vertex，並將MstVertex結構體傳入data。類似地，要將一條邊插入圖中，調用函數graph_ins_edge，並將MstVertex結構體傳入data1和data2 。當插入一個頂點時，只設置MstVertex結構體的data成員。當插入一條邊時，設置data1的data成員，data2的data和weight成員。在data2中，weight是邊的權值，此邊是data1中的頂點到data2中頂點的連接線。在實際中，權值通常用浮點數進行存儲和計算。由於鍵值是由權值計算來的，因此鍵值也用浮點數表示。
mst操作首先初始化鄰接表結構鍊表中的每個頂點。將每個頂點的鍵值初始化為DBL_MAX（除超始頂點外，超始頂點初始值為0.0）。在圖的抽象數據類型中，圖由一個鄰接表結構鍊表來表示。每個鄰接表包含一個頂點和一個相鄰頂點的集合。用存儲在鄰接表結構中的頂點來維護頂點的色值、鍵值、和父結點。維護鄰接表結構鍊表中信息的關鍵是能將這些信息存儲起來，而不是僅僅列出與自己相鄰的頂點。鑑於一個頂點可能會出現在眾多的鄰接表中，所以每個頂點只能在鄰接表結構鍊表中出現一次。
Prim算法的核心是用一個單循環為圖中的每個結點迭代一次。在每次迭代的過程中：
首先，在所有的白色頂點中選擇鍵值最小的頂點。 同時，在鄰接表結構鍊表把此頂點塗黑 。
接下來，遍歷與所選頂點相鄰的頂點。在遍歷每個頂點時，檢查它在鄰接表結構鍊表中的顏色和鍵值。一旦獲取了這些信息，就將它與所選頂點的顏色和鍵值進行比較。如果相鄰頂點是白色，且其鍵值比所選頂點的小，就將所選頂點與相鄰頂點之間邊的權值設置為相鄰頂點的鍵值；同時，將相鄰頂點的父結點設置為所選頂點。然後，更新存儲在鄰接表結構鍊表中相鄰頂點的信息。重複這個過程，直到所有頂點都塗黑。一旦Prim算法中的主循環結束，最小生成樹也就計算完成了。 此時，將鄰接表結構鍊表中的每個黑色MstVertex結構體插入到鍊表span中 。在span中，父結點為NULL的頂點就是最小生成樹的根結點。其他每個頂點的parent成員都指向span中位於該頂點之前的那個頂點。每個MstVertex結構體的成員weight並不經常使用，因為它只有在存儲到鄰接表中時才用的到。
下圖顯示了上面的示例圖中計算最小生成樹所返回的MstVertex結構體鍊表：
示例：圖算法的頭文件（含最小生成樹、最短路徑、旅行商問題三種實現所需函數定義的頭文件）#ifndef GRAPHALG_H#define GRAPHALG_H
#include "graph.h"#include "list.h"
typedef struct MstVertex_{ void *data; double weight; VertexColor color; double kdy; struct MstVertex_ *parent;}MstVertex;
typedef struct PathVertex_{ void *data; double weight; VertexColor color; double d; struct PathVertex_ *parent;}PathVertex;
typedef struct TspVertex_{ void *data; double x,y; VertexColor color;}TspVertex;
int mst(Graph *graph, const MstVertex *start, List *span, int (*match)(const void *key1, const void *key2));
int shortest(Graph *graph, const PathVertex *start, List *paths, int(*match)(const void *key1, const void *key2));
int tsp(List *vertexs, const TspVertex *start, List *tour, int (match*)(const void *key1, const void *key2));
#endif 示例：計算最小生成樹的實現
int mst(Graph *graph, const MstVertex *start, List *span, int (*match)(const void *key1, const void *key2)){ AdjList *adjlist; MstVertex *mst_vertex, *adj_vertex; ListElmt *element, *member; double minmum; int found,i;
found=0;
for(element=list_head(&graph_adjlists(graph)); element!=NULL; element = list_next(element)) { mst_vertex = ((AdjList *)list_data(element))->vertex;
if(match(mst_vertex,start)) { mst_vertex->color = white; mst_vertex->key = 0; mst_vertex->parent = NULL; found = 1; } else { mst_vertex->color = white; mst_vertex->key = DBL_MAX; mst_vertex->parent = NULL; } } if(!found ) return -1;
i=0;
while(i<graph_vcount(graph)) { minimum = DBL_MAX;
for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element)) { mst_vertex = ((AdjList *)list_data(element))->vertex;
if(mst_vertex->color == white && mst_vertex->key < minmum) { minmum = mst_vertex->key; adjlist = list_data(element); } } ((MstVertex *)adjlist->vertex)->color = black;
for(member = list_head(&adjlist->adjacent); member != NULL; member = list_next(member)) { adj_vertex = list_data(member);
for(element = list_head(&graph_adjlists(graph)); element != NULL; elemet = list_next(element)) { mst_vertex = ((AdjList *)list_data(element))->vertex;
if(match(mst_vertex,adj_vertex)) { if(mst_vertex->color == white && adj_vertex->weight < mst_vertex->key) { mst_vertex->key = adj_vertex->weight; mst_vertex->parent = adjlist_vertex; } break; } } } i++; }
list_init(span,NULL);for(element = list_head(&graph_adjlists(graph)); elemet != NULL; element = list_next(element)){ mst_vertex = ((AdjList *)list_data(element))->vertex;
if(mst_vertex->color == black) { if(list_ins_next(span, list_tail(span),mst_vertex) != 0) { list_destroy(span); return -1; } }} return 0;}
聲明：發布此文是出於傳遞更多知識以供交流學習之目的。若有來源標註錯誤或侵犯了您的合法權益，請作者持權屬證明與我們聯繫，我們將及時更正、刪除，謝謝。
作者：DreamGo
來源：http://www.cnblogs.com/idreamo/p/9472295.html
More：【微信公眾號】 u3dnotes