1. 圖的應用總覽

?? ?在數據結構中圖的應用很廣泛，本文主要從以下四個方面介紹：
?? ?①最小生成樹：給定一個無向網絡，在該網的所有生成樹中，使得各邊權數之和最小的那棵生成樹稱為該網的最小生成樹，也叫最小代價生成樹。
?? ?②拓撲排序：由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。
?? ?③關鍵路徑：在AOE-網中有些活動可以并行地進行，所以完成工程的最短時間是從開始點到完成點的最長路徑的長度，路徑長度最長的路徑叫做關鍵路徑(Critical Path)。
?? ?④最短路徑：最短路徑問題是圖研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。

2. 最小生成樹

問題提出：
?? ?要在n個城市間建立通信聯絡網。頂點：表示城市，權：城市間通信線路的花費代價。希望此通信網花費代價最小。
問題分析：
?? ?答案只能從生成樹中找，因為要做到任何兩個城市之間有線路可達，通信網必須是連通的；但對長度最小的要求可以知道網中顯然不能有圈，如果有圈，去掉一條邊后，并不破壞連通性，但總代價顯然減少了，這與總代價最小的假設是矛盾的。
結論：
?? ?希望找到一棵生成樹，它的每條邊上的權值之和（即建立該通信網所需花費的總代價）最小 —— 最小代價生成樹。
?? ?構造最小生成樹的算法很多，其中多數算法都利用了一種稱之為 MST 的性質。
?? ?MST 性質：設 N = (V, E) ?是一個連通網，U是頂點集 V的一個非空子集。若邊 (u, v) 是一條具有最小權值的邊，其中u∈U，v∈V-U，則必存在一棵包含邊 (u, v) 的最小生成樹。

（1）普里姆 (Prim) 算法

算法思想：?
?? ?①設 N=(V, E)是連通網，TE是N上最小生成樹中邊的集合。
?? ?②初始令 U={u_0}, (u_0∈V), TE={ }。
?? ?③在所有u∈U，u∈U-V的邊(u,v)∈E中，找一條代價最小的邊(u_0,v_0 )。
?? ?④將(u_0,v_0 )并入集合TE，同時v_0并入U。
?? ?⑤重復上述操作直至U = V為止，則 T=(V,TE)為N的最小生成樹。

?
代碼實現：

void MiniSpanTree_PRIM(MGraph G,VertexType u)//用普里姆算法從第u個頂點出發構造網G的最小生成樹T，輸出T的各條邊。//記錄從頂點集U到V-U的代價最小的邊的輔助數組定義；//closedge[j].lowcost表示在集合U中頂點與第j個頂點對應最小權值
{int k, j, i;k = LocateVex(G,u);for (j = 0; j < G.vexnum; ++j)	//輔助數組的初始化if(j != k){closedge[j].adjvex = u;closedge[j].lowcost = G.arcs[k][j].adj;	
//獲取鄰接矩陣第k行所有元素賦給closedge[j!= k].lowcost}closedge[k].lowcost = 0;		
//初始，U = {u};  PrintClosedge(closedge,G.vexnum);for (i = 1; i < G.vexnum; ++i)	\
//選擇其余G.vexnum-1個頂點，因此i從1開始循環{k = minimum(G.vexnum,closedge);		
//求出最小生成樹的下一個結點：第k頂點PrintMiniTree_PRIM(G, closedge, k); 	//輸出生成樹的邊closedge[k].lowcost = 0;				//第k頂點并入U集PrintClosedge(closedge,G.vexnum);for(j = 0;j < G.vexnum; ++j){                                           if(G.arcs[k][j].adj < closedge[j].lowcost)	
//比較第k個頂點和第j個頂點權值是否小于closedge[j].lowcost{closedge[j].adjvex = G.vexs[k];//替換closedge[j]closedge[j].lowcost = G.arcs[k][j].adj;PrintClosedge(closedge,G.vexnum);}}}
}

（2）克魯斯卡爾 (Kruskal) 算法

算法思想：?
?? ?①設連通網 ?N = (V, E )，令最小生成樹初始狀態為只有n個頂點而無邊的非連通圖，T=(V, { })，每個頂點自成一個連通分量。
?? ?②在 E 中選取代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上（即：不能形成環），則將此邊加入到T中；否則，舍去此邊，選取下一條代價最小的邊。
③依此類推，直至 T 中所有頂點都在同一連通分量上為止。
? ? ??
?? ?最小生成樹可能不惟一！

3. 拓撲排序

（1）有向無環圖

?? ?無環的有向圖，簡稱 DAG (Directed Acycline Graph) 圖。
?
有向無環圖在工程計劃和管理方面的應用：除最簡單的情況之外，幾乎所有的工程都可分為若干個稱作“活動”的子工程，并且這些子工程之間通常受著一定條件的約束，例如：其中某些子工程必須在另一些子工程完成之后才能開始。
對整個工程和系統，人們關心的是兩方面的問題：?
①工程能否順利進行；?
②完成整個工程所必須的最短時間。
對應到有向圖即為進行拓撲排序和求關鍵路徑。?
AOV網：?
?? ?用一個有向圖表示一個工程的各子工程及其相互制約的關系，其中以頂點表示活動，弧表示活動之間的優先制約關系，稱這種有向圖為頂點表示活動的網，簡稱AOV網(Activity On Vertex network)。
例如：排課表
? ? ??
AOV網的特點：
①若從i到j有一條有向路徑，則i是j的前驅；j是i的后繼。
②若< i , j >是網中有向邊，則i是j的直接前驅；j是i的直接后繼。
③AOV網中不允許有回路，因為如果有回路存在，則表明某項活動以自己為先決條件，顯然這是荒謬的。

問題： ? ?
?? ?問題：如何判別 AOV 網中是否存在回路？
?? ?檢測 AOV 網中是否存在環方法：對有向圖構造其頂點的拓撲有序序列，若網中所有頂點都在它的拓撲有序序列中，則該AOV網必定不存在環。

拓撲排序的方法：
?? ?①在有向圖中選一個沒有前驅的頂點且輸出之。
?? ?②從圖中刪除該頂點和所有以它為尾的弧。
?? ?③重復上述兩步，直至全部頂點均已輸出；或者當圖中不存在無前驅的頂點為止。
? ? ? ??
?? ?一個AOV網的拓撲序列不是唯一的！
代碼實現：
?

Status TopologicalSort(ALGraph G)//有向圖G采用鄰接表存儲結構。//若G無回路，則輸出G的頂點的一個拓撲序列并返回OK，否則返回ERROR.//輸出次序按照棧的后進先出原則，刪除頂點，輸出遍歷
{SqStack S;int i, count;int *indegree1 = (int *)malloc(sizeof(int) * G.vexnum);int indegree[12] = {0};FindInDegree(G, indegree);	//求個頂點的入度下標從0開始InitStack(&S);PrintStack(S);for(i = 0; i < G.vexnum; ++i)if(!indegree[i])		//建0入度頂點棧Spush(&S,i);		//入度為0者進棧count = 0;				//對輸出頂點計數while (S.base != S.top){ArcNode* p;pop(&S,&i);VisitFunc(G,i);//第i個輸出棧頂元素對應的頂點，也就是最后進來的頂點	++count;		  //輸出i號頂點并計數for(p = G.vertices[i].firstarc; p; p = p->nextarc){	//通過循環遍歷第i個頂點的表結點，將表結點中入度都減1int k = p->adjvex;	//對i號頂點的每個鄰接點的入度減1if(!(--indegree[k]))push(&S,k);		//若入度減為0，則入棧}//for}//whileif(count < G.vexnum){printf("\n該有向圖有回路!\n");return ERROR;	//該有向圖有回路}else{printf("\n該有向圖沒有回路!\n");return OK;}
}

關鍵路徑

?? ?把工程計劃表示為有向圖，用頂點表示事件，弧表示活動，弧的權表示活動持續時間。每個事件表示在它之前的活動已經完成，在它之后的活動可以開始。稱這種有向圖為邊表示活動的網，簡稱為 AOE網 (Activity On Edge)。
例如：
設一個工程有11項活動，9個事件。
事件v_1——表示整個工程開始（源點）?
事件v_9——表示整個工程結束（匯點）

?
對AOE網，我們關心兩個問題： ?
①完成整項工程至少需要多少時間？?
②哪些活動是影響工程進度的關鍵？
關鍵路徑——路徑長度最長的路徑。
路徑長度——路徑上各活動持續時間之和。
v_i——表示事件v_i的最早發生時間。假設開始點是v_1，從v_1到〖v?i〗的最長路徑長度。?(?)——表示活動a_i的最早發生時間。
l(?)——表示活動a_i最遲發生時間。在不推遲整個工程完成的前提下，活動a_i最遲必須開始進行的時間。
l(?)-?(?)意味著完成活動a_i的時間余量。
我們把l(?)=?(?)的活動叫做關鍵活動。顯然，關鍵路徑上的所有活動都是關鍵活動，因此提前完成非關鍵活動并不能加快工程進度。
?? ?例如上圖中網，從從v_1到v_9的最長路徑是(v_1,v_2,v_5,v_8,ν_9 )，路徑長度是18，即ν_9的最遲發生時間是18。而活動a_6的最早開始時間是5，最遲開始時間是8，這意味著：如果a_6推遲3天或者延遲3天完成，都不會影響整個工程的完成。因此，分析關鍵路徑的目的是辨別哪些是關鍵活動，以便爭取提高關鍵活動的工效，縮短整個工期。
?? ?由上面介紹可知：辨別關鍵活動是要找l(?)=?(?)的活動。為了求?(?)和l(?)，首先應求得事件的最早發生時間v?(j)和最遲發生時間vl(j)。如果活動a_i由弧?j,k?表示，其持續時間記為dut(?j,k?),則有如下關系：
?(?)= v?(j)
l(?)=vl(k)-dut(?j,k?)
?? ?求v?(j)和vl(j)需分兩步進行：
第一步：從v?(0)=0開始向前遞推
v?(j)=Max{v?(i)+dut(?j,k?)} ? ?i,j?∈T,j=1,2,…,n-1
其中，T是所有以第j個頂點為頭的弧的集合。
第二步：從vl(n-1)=v?(n-1)起向后遞推
vl(i)=Min{vl(j)-dut(?i,j?)} ??i,j?∈S,i=n-2,…,0
其中，S是所有以第i個頂點為尾的弧的集合。
下面我們以上圖AOE網為例，先求每個事件v_i的最早發生時間，再逆向求每個事件對應的最晚發生時間。再求每個活動的最早發生時間和最晚發生時間，如下面表格：
? ? ? ? ??
在活動的統計表中，活動的最早發生時間和最晚發生時間相等的，就是關鍵活動

關鍵路徑的討論：

①若網中有幾條關鍵路徑，則需加快同時在幾條關鍵路徑上的關鍵活動。 ? ? ?如：a11、a10、a8、a7。?
②如果一個活動處于所有的關鍵路徑上，則提高這個活動的速度，就能縮短整個工程的完成時間。如：a1、a4。
③處于所有關鍵路徑上的活動完成時間不能縮短太多，否則會使原關鍵路徑變成非關鍵路徑。這時必須重新尋找關鍵路徑。如：a1由6天變成3天，就會改變關鍵路徑。

關鍵路徑算法實現：

int CriticalPath(ALGraph G)
{	//因為G是有向網，輸出G的各項關鍵活動SqStack T;int i, j;	ArcNode* p;int k , dut;if(!TopologicalOrder(G,T))return 0;int vl[VexNum];for (i = 0; i < VexNum; i++)vl[i] = ve[VexNum - 1];		//初始化頂點事件的最遲發生時間while (T.base != T.top)			//按拓撲逆序求各頂點的vl值{for(pop(&T, &j), p = G.vertices[j].firstarc; p; p = p->nextarc){k = p->adjvex;	dut = *(p->info);	//dut<j, k>if(vl[k] - dut < vl[j])vl[j] = vl[k] - dut;}//for}//whilefor(j = 0; j < G.vexnum; ++j)	//求ee,el和關鍵活動{for (p = G.vertices[j].firstarc; p; p = p->nextarc){int ee, el;		char tag;k = p->adjvex;	dut = *(p->info);ee = ve[j];	el = vl[k] - dut;tag = (ee == el) ? '*' : ' ';PrintCriticalActivity(G,j,k,dut,ee,el,tag);}}return 1;
}

?

?

4.最短路

?? ?典型用途：交通網絡的問題——從甲地到乙地之間是否有公路連通？在有多條通路的情況下，哪一條路最短？
?
?? ?交通網絡用有向網來表示：頂點——表示城市，弧——表示兩個城市有路連通，弧上的權值——表示兩城市之間的距離、交通費或途中所花費的時間等。
?? ?如何能夠使一個城市到另一個城市的運輸時間最短或運費最省？這就是一個求兩座城市間的最短路徑問題。
?? ?問題抽象：在有向網中A點（源點）到達B點（終點）的多條路徑中，尋找一條各邊權值之和最小的路徑，即最短路徑。最短路徑與最小生成樹不同，路徑上不一定包含n個頂點，也不一定包含n - 1條邊。
? ?常見最短路徑問題：單源點最短路徑、所有頂點間的最短路徑
（1）如何求得單源點最短路徑？
?? ?窮舉法：將源點到終點的所有路徑都列出來，然后在其中選最短的一條。但是，當路徑特別多時，特別麻煩；沒有規律可循。
?? ?迪杰斯特拉（Dijkstra）算法：按路徑長度遞增次序產生各頂點的最短路徑。
路徑長度最短的最短路徑的特點：
?? ?在此路徑上，必定只含一條弧 <v_0, v_1>，且其權值最小。由此，只要在所有從源點出發的弧中查找權值最小者。
下一條路徑長度次短的最短路徑的特點：
①、直接從源點到v_2<v_0, v_2>（只含一條弧）；
②、從源點經過頂點v_1，再到達v_2<v_0, v_1>,<v_1, v_2>（由兩條弧組成）
再下一條路徑長度次短的最短路徑的特點：
?? ?有以下四種情況：
?? ?①、直接從源點到v_3<v_0, v_3>（由一條弧組成）；
?? ?②、從源點經過頂點v_1，再到達v_3<v_0, v_1>,<v_1, v_3>（由兩條弧組成）；
?? ?③、從源點經過頂點v_2，再到達v_3<v_0, v_2>,<v_2, v_3>（由兩條弧組成）；
?? ?④、從源點經過頂點v_1 ?,v_2，再到達v_3<v_0, v_1>,<v_1, v_2>,<v_2, v_3>（由三條弧組成）；
其余最短路徑的特點:?? ?
?? ?①、直接從源點到v_i<v_0, v_i>（只含一條弧）；
?? ?②、從源點經過已求得的最短路徑上的頂點，再到達v_i（含有多條弧）。
Dijkstra算法步驟：
?? ?初始時令S={v_0}, ?T={其余頂點}。T中頂點對應的距離值用輔助數組D存放。
?? ?D[i]初值：若<v_0, v_i>存在，則為其權值；否則為∞。?
?? ?從T中選取一個其距離值最小的頂點v_j，加入S。對T中頂點的距離值進行修改：若加進v_j作中間頂點，從v_0到v_i的距離值比不加 vj 的路徑要短，則修改此距離值。
?? ?重復上述步驟，直到 S = V 為止。

算法實現：

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{ // 用Dijkstra算法求有向網 G 的 v0 頂點到其余頂點v的最短路徑P[v]及帶權長度D[v]。// 若P[v][w]為TRUE,則 w 是從 v0 到 v 當前求得最短路徑上的頂點。  P是存放最短路徑的矩陣，經過頂點變成TRUE// final[v]為TRUE當且僅當 v∈S,即已經求得從v0到v的最短路徑。int v,w,i,j,min;Status final[MAX_VERTEX_NUM];for(v = 0 ;v < G.vexnum ;++v){final[v] = FALSE;D[v] = G.arcs[v0][v].adj;		//將頂點數組中下標對應是 v0 和 v的距離給了D[v]for(w = 0;w < G.vexnum; ++w)P[v][w] = FALSE;			//設空路徑if(D[v] < INFINITY){P[v][v0] = TRUE;P[v][v] = TRUE;}}D[v0]=0;final[v0]= TRUE; /* 初始化,v0頂點屬于S集 */for(i = 1;i < G.vexnum; ++i) /* 其余G.vexnum-1個頂點 */{ /* 開始主循環,每次求得v0到某個v頂點的最短路徑,并加v到S集 */min = INFINITY; /* 當前所知離v0頂點的最近距離 */for(w = 0;w < G.vexnum; ++w)if(!final[w]) /* w頂點在V-S中 */if(D[w] < min){v = w;min = D[w];} /* w頂點離v0頂點更近 */final[v] = TRUE; /* 離v0頂點最近的v加入S集 */for(w = 0;w < G.vexnum; ++w) /* 更新當前最短路徑及距離 */{if(!final[w] && min < INFINITY && G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w])){ /* 修改D[w]和P[w],w∈V-S */D[w] = min + G.arcs[v][w].adj;for(j = 0;j < G.vexnum;++j)P[w][j] = P[v][j];P[w][w] = TRUE;}}}
}