友情鏈接：資料結構專欄

圖

【知識框架】

【考綱內容】

• 圖的基本概念
• 圖的存盤及基本操作
  • 鄰接矩陣法;鄰接表法;鄰接多重表;十字鏈表
• 圖的遍歷
  • 深度優先搜索;廣度優先搜索
• 圖的基本應用
  • 最小(代價)生成樹;最短路徑;拓撲排序;關鍵路徑

圖的基本概念

在線性表中，資料元素之間是被串起來的，僅有線性關系，每個資料元素只有一個直接前驅和一個直接后繼，在樹形結構中，資料元素之間有著明顯的層次關系，并且每一層上的資料元素可能和下一層中多個元素相關，但只能和上一層中一個元素相關，圖是一種較線性表和樹更加復雜的資料結構，在圖形結構中，結點之間的關系可以是任意的，圖中任意兩個資料元素之間都可能相關，

一、圖的定義

圖(Graph)是由頂點的有窮非空集合 V ( G ) V(G) V(G)和頂點之間邊的集合 E ( G ) E(G) E(G)組成，通常表示為: G = ( V , E ) G=(V,E) G=(V,E)，其中， G G G表示個圖， V V V是圖 G G G中頂點的集合， E E E是圖 G G G中邊的集合，若 V = { v 1 , v 2 , . . . , v n } V= \{v_1, v_2,...,v_n\} V={v1?,v2?,...,vn?}，則用 ∣ V ∣ |V| ∣V∣表示圖 G G G中頂點的個數，也稱圖 G G G的階， E = { ( u , v ) ∣ u ∈ V , v ∈ V } E= \{(u, v) |u∈V, v∈V\} E={(u,v)∣u∈V,v∈V}，用 ∣ E ∣ |E| ∣E∣表示圖 G G G中邊的條數，

注意:線性表可以是空表，樹可以是空樹，但圖不可以是空圖，就是說，圖中不能一個頂點也沒有，圖的頂點集V一定非空，但邊集E可以為空，此時圖中只有頂點而沒有邊，

二、圖的基本概念和術語

1、有向圖

若E是有向邊(也稱弧)的有限集合時，則圖G為有向圖，弧是頂點的有序對，記為<v, w>，其中v,w是頂點，v稱為弧尾，w稱為弧頭，<v,w>稱為從頂點v到頂點w的弧，也稱v鄰接到w，或w鄰接自v，

圖(a)所示的有向圖 G 1 G_1 G1?可表示為 G 1 = ( V 1 , E 1 ) G_1 = (V_1,E_1) G1?=(V1?,E1?) V 1 = { 1 , 2 , 3 } V_1=\{1,2,3\} V1?={1,2,3} E 1 = { < 1 , 2 > , < 2 , 1 > , < 2 , 3 > } E_1=\{<1,2>,<2,1>,<2,3>\} E1?={<1,2>,<2,1>,<2,3>}

2、無向圖

若E是無向邊(簡稱邊)的有限集合時，則圖G為無向圖，邊是頂點的無序對，記為(v, w)或(w,v),因為(v,w)=(w,v), 其中v,w是頂點，可以說頂點w和頂點v互為鄰接點，邊(v, w)依附于頂點w和v，或者說邊(v, w)和頂點v, w相關聯，

圖(b)所示的無向圖G2可表示為 G 2 = ( V 2 , E 2 ) G_2=(V_2,E_2) G2?=(V2?,E2?) V 2 = { 1 , 2 , 3 , 4 } V_2=\{1,2,3,4\} V2?={1,2,3,4} E 2 = { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } E_2=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\} E2?={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

3、簡單圖

一個圖 G G G若滿足:①不存在重復邊;②不存在頂點到自身的邊，則稱圖 G G G為簡單圖，上圖中 G 1 G_1 G1?和 G 2 G_2 G2?均為簡單圖，資料結構中僅討論簡單圖，

4、多重圖

若圖 G G G中某兩個結點之間的邊數多于一條，又允許頂點通過同一條邊和自己關聯，則 G G G為多重圖，多重圖的定義和簡單圖是相對的，

5、完全圖（也稱簡單完全圖）

對于無向圖， ∣ E ∣ |E| ∣E∣的取值范圍是 0 0 0到 n ( n ? 1 ) / 2 n(n-1)/2 n(n?1)/2，有 n ( n ? 1 ) / 2 n(n -1)/2 n(n?1)/2條邊的無向圖稱為完全圖，在完全圖中任意兩個頂點之間都存在邊，對于有向圖， ∣ E ∣ |E| ∣E∣的取值范圍是 0 0 0到 n ( n ? 1 ) n(n-1) n(n?1)，有 n ( n ? 1 ) n(n-1) n(n?1)潭訓的有向圖稱為有向完全圖，在有向完全圖中任意兩個頂點之間都存在方向相反的兩潭訓，上圖中 G 2 G_2 G2?為無向完全圖，而 G 3 G_3 G3?為有向完全圖，

6、子圖

設有兩個圖 G = ( V , E ) G=(V, E) G=(V,E)和 G ′ = ( V ′ , E ′ ) G'=(V', E') G′=(V′,E′)， 若 V ′ V' V′是 V V V的子集，且 E ′ E' E′是 E E E的子集，則稱 G ′ G' G′是 G G G的子圖，若有滿足 V ( G ′ ) = V ( G ) V(G')= V(G) V(G′)=V(G)的子圖 G ′ G' G′，則稱其為 G G G的生成子圖，上圖中 G 3 G_3 G3?為 G 1 G_1 G1?的子圖，

注意:并非V和E的任何子集都能構成G的子圖，因為這樣的子集可能不是圖，即E的子集中的某些邊關聯的頂點可能不在這個V的子集中，

7、連通、連通圖和連通分量

在無向圖中，若從頂點 v v v到頂點 w w w有路徑存在，則稱 v v v和 w w w是連通的，若圖 G G G中任意兩個頂點都是連通的，則稱圖 G G G為連通圖，否則稱為非連通圖，無向圖中的極大連通子圖稱為連通分量，若一個圖有 n n n個頂點，并且邊數小于 n ? 1 n-1 n?1，則此圖必是非連通圖，如下圖(a)所示， 圖 G 4 G_4 G4?有3個連通分量，如圖（b）所示，

注意:弄清連通、連通圖、連通分量的概念非常重要，首先要區分極大連通子圖和極小連通子圖，極大連通子圖是無向圖的連通分量，極大即要求該連通子圖包含其所有的邊;極小連通子圖是既要保持圖連通又要使得邊數最少的子圖，

8、強連通圖、強連通分量

在有向圖中，若從頂點 v v v到頂點 w w w和從頂點 w w w到項點 v v v之間都有路徑,則稱這兩個頂點是強連通的，若圖中任何一對頂點都是強連通的，則稱此圖為強連通圖，有向圖中的極大強連通子圖稱為有向圖的強連通分量，圖 G 1 G_1 G1?的強連通分量如下圖所示，

注意:強連通圖、強連通分量只是針對有向圖而言的，一般在無向圖中討論連通性，在有向圖中考慮強連通性，

9、生成樹、生成森林

連通圖的生成樹是包含圖中全部頂點的一個極小連通子圖，若圖中頂點數為 n n n,則它的生成樹含有 n ? 1 n-1 n?1條邊，對生成樹而言，若砍去它的一條邊，則會變成非連通圖，若加上一條邊則會形成一個回路，在非連通圖中，連通分量的生成樹構成了非連通圖的生成森林，圖 G 2 G_2 G2?的一個生成樹如下圖所示，

注意:包含無向圖中全部頂點的極小連通子圖，只有生成樹滿足條件，因為砍去生成樹的任一條邊，圖將不再連通，

10、頂點的度、入度和出度

圖中每個頂點的度定義為以該項點為一個端點的邊的數目，
對于無向圖，頂點v的度是指依附于該頂點的邊的條數，記為 T D ( v ) TD(v) TD(v)，
在具有 n n n個頂點、 e e e條邊的無向圖中， ∑ i = 1 n T D ( v i ) = 2 e \displaystyle\sum_{i=1}^{n}TD(v_i)= 2e i=1∑n?TD(vi?)=2e，即無向圖的全部頂點的度的和等于邊數的2倍，因為每條邊和兩個頂點相關聯，
對于有向圖,頂點 v v v的度分為入度和出度,入度是以頂點 v v v為終點的有向邊的數目，記為 I D ( v ) ID(v) ID(v); 而出度是以頂點 v v v為起點的有向邊的數目，記為 O D ( v ) OD(v) OD(v)，頂點 v v v的度等于其入度和出度之和，即 T D ( v ) = I D ( v ) + O D ( v ) ， TD(v) = ID(v) + OD(v)， TD(v)=ID(v)+OD(v)，
在具有 n n n個頂點、 e e e條邊的有向圖中， ∑ i = 1 n I D ( v i ) = ∑ i = 1 n O D ( v i ) = e \displaystyle\sum_{i=1}^{n}ID(v_i)=\displaystyle\sum_{i=1}^{n}OD(v_i)=e i=1∑n?ID(vi?)=i=1∑n?OD(vi?)=e，即有向圖的全部頂點的入度之和與出度之和相等，并且等于邊數，這是因為每條有向邊都有一個起點和終點，

11、邊的權和網

在一個圖中，每條邊都可以標上具有某種含義的數值，該數值稱為該邊的權值，這種邊上帶有權值的圖稱為帶權圖，也稱網，

12、稠密圖、稀疏圖

邊數很少的圖稱為稀疏圖，反之稱為稠密圖，稀疏和稠密本身是模糊的概念，稀疏圖和稠密圖常常是相對而言的，一般當圖G滿足 ∣ E ∣ < ∣ V ∣ l o g ∣ V ∣ |E| < |V|log|V| ∣E∣<∣V∣log∣V∣時，可以將 G G G視為稀疏圖，

13、路徑、路徑長度和回路

頂點 v p v_p vp?到頂點 v q v_q vq?之間的一條路徑是指頂點序列 v p , v i 1 , v i 2 , . . . , v i m , v q v_p,v_{i_1},v_{i_2},...,v_{i_m},v_q vp?,vi1??,vi2??,...,vim??,vq?，當然關聯的邊也可以理解為路徑的構成要素，路徑上邊的數目稱為路徑長度，第一個頂點和最后一個頂點相同的路徑稱為回路或環，若一個圖有 n n n個頂點，并且有大于 n ? 1 n-1 n?1條邊，則此圖一定有環，

14、 簡單路徑、簡單回路

在路徑序列中，頂點不重復出現的路徑稱為簡單路徑，除第一個頂點和最后一個頂點外，其余頂點不重復出現的回路稱為簡單回路，

15、距離

從頂點 u u u出發到頂點 v v v的最短路徑若存在，則此路徑的長度稱為從 u u u到 v v v的距離，若從 u u u到 v v v根本不存在路徑，則記該距離為無窮 ( ∞ ) (∞) (∞)，

16、有向樹

一個頂點的入度為0、其余頂點的入度均為1的有向圖，稱為有向樹，

圖的存盤結構

由于圖的結構比較復雜，任意兩個頂點之間都可能存在聯系，因此無法以資料元素在記憶體中的物理位置來表示元素之間的關系，也就是說，圖不可能用簡單的順序存盤結構來表示，而多重鏈表的方式，要么會造成很多存盤單元的浪費，要么又帶來操作的不便，因此，對于圖來說，如何對它實作物理存盤是個難題，接下來我們介紹五種不同的存盤結構，

一、鄰接矩陣

圖的鄰接矩陣(Adjacency Matrix) 存盤方式是用兩個陣列來表示圖，一個一維陣列存盤圖中頂點資訊，一個二維陣列(稱為鄰接矩陣)存盤圖中的邊或弧的資訊，
設圖 G G G有 n n n個頂點，則鄰接矩陣 A A A是一個 n ? n n*n n?n的方陣，定義為:

下圖是一個無向圖和它的鄰接矩陣：

可以看出:

1. 無向圖的鄰接矩陣一定是一個對稱矩陣(即從矩陣的左上角到右下角的主對角線為軸，右上角的元與左下角相對應的元全都是相等的)， 因此，在實際存盤鄰接矩陣時只需存盤上(或下)三角矩陣的元素，
2. 對于無向圖，鄰接矩陣的第 i i i行(或第 i i i列)非零元素(或非 ∞ ∞ ∞元素)的個數正好是第 i i i個頂點的度 T D ( v i ) TD(v_i) TD(vi?)，比如頂點 v 1 v_1 v1?的度就是 1 + 0 + 1 + 0 = 2 1+0+1+0=2 1+0+1+0=2，
3. 求頂點 v i v_i vi?的所有鄰接點就是將矩陣中第i行元素掃描一遍， A [ i ] [ j ] A[i][j] A[i][j]為 1就是鄰接點，

---

下圖是有向圖和它的鄰接矩陣：

可以看出:

1. 主對角線上數值依然為0，但因為是有向圖，所以此矩陣并不對稱，
2. 有向圖講究入度與出度，頂點 v 1 v_1 v1?的入度為1,正好是第 v 1 v_1 v1?列各數之和，頂點 v 1 v_1 v1?的出度為2，即第 v 1 v_1 v1?行的各數之和，
3. 與無向圖同樣的辦法，判斷頂點 v i v_i vi?到 v j v_j vj?是否存在弧，只需要查找矩陣中 A [ i ] [ j ] A[i][j] A[i][j] 是否為1即可，

---

對于帶權圖而言,若頂點 v i v_i vi?和 v j v_j vj?之間有邊相連，則鄰接矩陣中對應項存放著該邊對應的權值

下圖是有向網圖和它的鄰接矩陣：

---

通過以上對無向圖、有向圖和網的描述，可定義出鄰接矩陣的存盤結構：

#define MaxVertexNum 100;	//頂點數目的最大值
typedef char VertexType;	//頂點的資料型別
typedef int EdgeType;	//帶權圖中邊上權值的資料型別
typedef struct{
	VertexType Vex[MaxVertexNum];	//頂點表
	EdgeType Edge[MaxVertexNum][MaxVertexNum];	//鄰接矩陣，邊表
	int vexnum, arcnum;	//圖的當前頂點數和弧樹
}MGraph;

---

注意:
①在簡單應用中，可直接用二維陣列作為圖的鄰接矩陣(頂點資訊等均可省略)，
②當鄰接矩陣中的元素僅表示相應的邊是否存在時，EdgeType可定義為值為0和1的列舉型別，
③無向圖的鄰接矩陣是對稱矩陣，對規模特大的鄰接矩陣可采用壓縮存盤，
④鄰接矩陣表示法的空間復雜度為 O ( n 2 ) O(n^2) O(n2)， 其中n為圖的頂點數 ∣ V ∣ |V| ∣V∣，
⑤ 用鄰接矩陣法存盤圖，很容易確定圖中任意兩個頂點之間是否有邊相連，但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大，
⑥ 稠密圖適合使用鄰接矩陣的存盤表示，

二、鄰接表

當一個圖為稀疏圖時（邊數相對頂點較少），使用鄰接矩陣法顯然要浪費大量的存盤空間，如下圖所示：

而圖的鄰接表法結合了順序存盤和鏈式存盤方法，大大減少了這種不必要的浪費，
所謂鄰接表，是指對圖 G G G中的每個頂點 v i v_i vi?建立一個單鏈表，第 i i i個單鏈表中的結點表示依附于頂點 v i v_i vi? 的邊(對于有向圖則是以頂點 v i v_i vi?為尾的弧)，這個單鏈表就稱為頂點 v i v_i vi?的邊表(對于有向圖則稱為出邊表)，邊表的頭指標和頂點的資料資訊采用順序存盤(稱為頂點表)，所以在鄰接表中存在兩種結點:頂點表結點和邊表結點，如下圖所示，

頂點表結點由頂點域(data)和指向第一條鄰接邊的指標(firstarc) 構成，邊表(鄰接表)結點由鄰接點域(adjvex)和指向下一條鄰接邊的指標域(nextarc) 構成，
無向圖的鄰接表的實體如下圖所示，

有向圖的鄰接表的實體如下圖所示，

此時我們很容易就可以算出某個頂點的入度或出度是多少，判斷兩頂點是否存在弧也很容易實作，
對于帶權值的網圖，可以在邊表結點定義中再增加一個weight的資料域，存盤權值資訊即可，

圖的鄰接表存盤結構定義如下：

#define MAXVEX 100;	//圖中頂點數目的最大值
type char VertexType;	//頂點型別應由用戶定義
typedef int EdgeType;	//邊上的權值型別應由用戶定義
/*邊表結點*/
typedef struct EdgeNode{
	int adjvex;	//該弧所指向的頂點的下標或者位置
	EdgeType weight;	//權值，對于非網圖可以不需要
	struct EdgeNode *next;	//指向下一個鄰接點
}EdgeNode;

/*頂點表結點*/
typedef struct VertexNode{
	Vertex data;	//頂點域，存盤頂點資訊
	EdgeNode *firstedge	//邊表頭指標
}VertexNode, AdjList[MAXVEX];

/*鄰接表*/
typedef struct{
	AdjList adjList;
	int numVertexes, numEdges;	//圖中當前頂點數和邊數
}

圖的鄰接表存盤方法具有以下特點

1. 若 G G G為無向圖，則所需的存盤空間為 O ( ∣ V ∣ + 2 ∣ E ∣ ) O(|V|+2|E|) O(∣V∣+2∣E∣)；若 G G G為有向圖,則所需的存盤空間為 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣)，前者的倍數2是由于無向圖中,每條邊在鄰接表中出現了兩次
2. 對于稀疏圖，采用鄰接表表示將極大地節省存盤空間，
3. 在鄰接表中，給定一頂點，能很容易地找出它的所有鄰邊，因為只需要讀取它的鄰接表，在鄰接矩陣中，相同的操作則需要掃描一行，花費的時間為 O ( n ) O(n) O(n)，但是，若要確定給定的兩個頂點間是否存在邊，則在鄰接矩陣中可以立刻查到，而在鄰接表中則需要在相應結點對應的邊表中查找另一結點，效率較低，
4. 在有向圖的鄰接表表示中，求一個給定頂點的出度只需計算其鄰接表中的結點個數；但求其頂點的入度則需要遍歷全部的鄰接表，因此,也有人采用逆鄰接表的存盤方式來加速求解給定頂點的入度，當然,這實際上與鄰接表存盤方式是類似的，
5. 圖的鄰接表表示并不唯一，因為在每個頂點對應的單鏈表中，各邊結點的鏈接次序可以是任意的，它取決于建立鄰接表的演算法及邊的輸入次序，

三、十字鏈表

十字鏈表是有向圖的一種鏈式存盤結構，
對于有向圖來說，鄰接表是有缺陷的，關心了出度問題，想了解入度就必須要遍歷整個圖才能知道，反之，逆鄰接表解決了入度卻不了解出度的情況，有沒有可能把鄰接表與逆鄰接表結合起來呢?答案是肯定的，就是把它們整合在一起，這就是我們現在要介紹的有向圖的一種存盤方法：十字鏈表(Orthogonal List)，
我們重新定義頂點表結點結構如下表所示，

其中firstin表示入邊表頭指標，指向該頂點的入邊表中第一個結點，firstout 表示出邊表頭指標，指向該頂點的出邊表中的第一個結點，
重新定義的邊表結點結構如下表所示，

其中tailvex 是指弧起點在頂點表的下標，headvex 是指弧終點在頂點表中的下標，headlink是指入邊表指標域，指向終點相同的下一條邊，taillink是指邊表指標域，指向起點相同的下一條邊，如果是網，還可以再增加一個weight域來存盤權值，

接下來通過一個例子詳細介紹十字鏈表的結構，
如下圖所示，頂點依然是存入一個一維陣列 { V 0 , V 1 , V 2 , V 3 } \{V_0,V_1,V_2,V_3\} {V0?,V1?,V2?,V3?}，實線箭頭指標的圖示完全與的鄰接表的結構相同，就以頂點 V 0 V_0 V0?來說，firstout 指向的是出邊表中的第一個結點 V 3 V_3 V3?，所以 V 0 V_0 V0?邊表結點的 h e a d v e x = 3 headvex=3 headvex=3，而tailvex就是當前頂點 V 0 V_0 V0?的下標0，由于 V 0 V_0 V0?只有一個出邊頂點，所以headlink和taillink都是空，

我們重點需要來解釋虛線箭頭的含義，它其實就是此圖的逆鄰接表的表示，對于 V 0 V_0 V0?來說，它有兩個頂點 V 1 V_1 V1?和 V 2 V_2 V2?的入邊，因此 V 0 V_0 V0?的firstin指向頂點 V 1 V_1 V1?的邊表結點中headvex為0的結點，如上圖右圖中的①，接著由入邊結點的headlink指向下一個入邊頂點 V 2 V_2 V2?，如圖中的②，對于頂點 V 1 V_1 V1?,它有一個入邊頂點 V 2 V_2 V2?，所以它的firstin指向頂點 V 2 V_2 V2?的邊表結點中headvex為1的結點，如圖中的③，頂點 V 2 V_2 V2?和 V 3 V_3 V3?也是同樣有一個入邊頂點，如圖中④和⑤，

十字鏈表的好處就是因為把鄰接表和逆鄰接表整合在了一起， 這樣既容易找到以 V 1 V_1 V1?為尾的弧，也容易找到以 V 1 V_1 V1?為頭的弧，因而容易求得頂點的出度和入度，而且它除了結構復雜一點外，其實創建圖演算法的時間復雜度是和鄰接表相同的，因此，在有向圖的應用中，十字鏈表是非常好的資料結構模型，

四、鄰接多重表

鄰接多重表是無向圖的另一種鏈式存盤結構，
在鄰接表中，容易求得頂點和邊的各種資訊，但在鄰接表中求兩個頂點之間是否存在邊而對邊執行洗掉等操作時，需要分別在兩個頂點的邊表中遍歷，效率較低，比如下圖中，若要洗掉左圖的 ( V 0 , V 2 ) (V_0,V_2) (V0?,V2?) 這條邊，需要對鄰接表結構中右邊表的陰影兩個結點進行洗掉操作，顯然這是比較煩瑣的，

重新定義的邊表結點結構如下表所示，

其中ivex和jvex是與某條邊依附的兩個頂點在頂點表中下標，ilink 指向依附頂點ivex的下一條邊，jlink 指向依附頂點jvex的下一條邊，這就是鄰接多重表結構，

每個頂點也用一一個結點表示，它由如下所示的兩個域組成，

其中，data 域存盤該頂點的相關資訊，firstedge 域指示第一條依附于該頂點的邊，

我們來看結構示意圖的繪制程序，理解了它是如何連線的，也就理解鄰接多重表構造原理了，如下圖7所示，左圖告訴我們它有4個頂點和5條邊，顯然，我們就應該先將4個頂點和5條邊的邊表結點畫出來，

我們開始連線，如圖，首先連線的①②③④就是將頂點的firstedge指向一條邊，頂點下標要與ivex的值相同,這很好理解，接著，由于頂點 V 0 V_0 V0?的 ( V 0 , V 1 ) (V_0,V_1) (V0?,V1?) 邊的鄰邊有 ( V 0 , V 3 ) (V_0,V_3) (V0?,V3?) 和 ( V 0 , V 2 ) (V_0,V_2) (V0?,V2?)， 因此⑤⑥的連線就是滿足指向下一條依附于頂點 V 0 V_0 V0?的邊的目標，注意ilink指向的結點的jvex一定要和它本身的ivex的值相同，同樣的道理，連線⑦就是指 ( V 1 , V 0 ) (V_1,V_0) (V1?,V0?) 這條邊，它是相當于頂點 V 1 V_1 V1?指向 ( V 1 , V 2 ) (V_1,V_2) (V1?,V2?) 邊后的下一條， V 2 V_2 V2?有三條邊依附，所以在③之后就有了⑧⑨，連線④的就是頂點 V 3 V_3 V3?在連線④之后的下一條邊， 左圖一共有5條邊，所以右圖有10條連線，完全符合預期，

---

到這里，可以明顯的看出，鄰接多重表與鄰接表的差別，僅僅是在于同一條邊在鄰接表中用兩個結點表示，而在鄰接多重表中只有一個結點， 這樣對邊的操作就方便多了，若要洗掉左圖的 ( V 0 , V 2 ) (V_0,V_2) (V0?,V2?) 這條邊，只需要將右圖的⑥⑨的鏈接指向改為NULL即可，

五、邊集陣列

邊集陣列是由兩個一維陣列構成，一個是存盤頂點的資訊;另一個是存盤邊的資訊，這個邊陣列每個資料元素由一條邊的起點下標(begin)、 終點下標(end)和權(weight)組成，如下圖所示，顯然邊集陣列關注的是邊的集合，在邊集陣列中要查找一個頂點的度需要掃描整個邊陣列，效率并不高，因此它更適合對邊依次進行處理的操作，而不適合對頂點相關的操作，

圖的遍歷

圖的遍歷是和樹的遍歷類似，我們希望從圖中某一頂點出發訪遍圖中其余頂點，且使每一個頂點僅被訪問一次， 這一程序就叫做圖的遍歷(Traversing Graph)，
對于圖的遍歷來，通常有兩種遍歷次序方案:它們是深度優先遍歷和廣度優先遍歷，

一、深度優先遍歷

深度優先遍歷(Depth First Search)，也有稱為深度優先搜索，簡稱為DFS，

1、DFS演算法

深度優先搜索類似于樹的先序遍歷，如其名稱中所暗含的意思一樣，這種搜索演算法所遵循的搜索策略是盡可能“深”地搜索一個圖，它的基本思想如下:首先訪問圖中某一起始頂點v，然后由v出發，訪問與v鄰接且未被訪問的任一頂點 w 1 w_1 w1?，再訪問與 w 1 w_1 w1?鄰接且未被訪問的任一頂點…重復上述程序，當不能再繼續向下訪問時，依次退回到最近被訪問的頂點，若它還有鄰接頂點未被訪問過，則從該點開始繼續上述搜索程序，直至圖中所有頂點均被訪問過為止，
般情況下，其遞回形式的演算法十分簡潔，演算法程序如下:

bool visited[MAX_VERTEX_NUM];	//訪問標記陣列
/*從頂點出發，深度優先遍歷圖G*/
void DFS(Graph G, int v){
	int w;
	visit(v);	//訪問頂點
	visited[v] = TRUE;	//設已訪問標記
	//FirstNeighbor(G,v):求圖G中頂點v的第一個鄰接點，若有則回傳頂點號，否則回傳-1，
	//NextNeighbor(G,v,w):假設圖G中頂點w是頂點v的一個鄰接點，回傳除w外頂點v
	for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){
		if(!visited[w]){	//w為u的尚未訪問的鄰接頂點
			DFS(G, w);
		}
	}
}
/*對圖進行深度優先遍歷*/
void DFSTraverse(MGraph G){
	int v; 
	for(v=0; v<G.vexnum; ++v){
		visited[v] = FALSE;	//初始化已訪問標記資料
	}
	for(v=0; v<G.vexnum; ++v){	//從v=0開始遍歷
		if(!visited[v]){
			DFS(G, v);
		}
	}
}

以下面這個無向圖為例

其深度優先遍歷的結果為 a b d e h c f g abdehcfg abdehcfg

2、DFS演算法的性能分析

DFS演算法是一一個遞 歸演算法，需要借助一個遞回作業堆疊，故其空間復雜度為 O ( V ) O(V) O(V)，
對于n個頂點e條邊的圖來說，鄰接矩陣由于是二維陣列，要查找每個頂點的鄰接點需要訪問矩陣中的所有元素，因此都需要 O ( V 2 ) O(V^2) O(V2)的時間，而鄰接表做存盤結構時，找鄰接點所需的時間取決于頂點和邊的數量，所以是 O ( V + E ) O(V+E) O(V+E)， 顯然對于點多邊少的稀疏圖來說，鄰接表結構使得演算法在時間效率上大大提高，
對于有向圖而言，由于它只是對通道存在可行或不可行，演算法上沒有變化，是完全可以通用的，

3、深度優先的生成樹和生成森林

深度優先搜索會產生一棵深度優先生成樹， 當然，這是有條件的，即對連通圖呼叫DFS才能產生深度優先生成樹，否則產生的將是深度優先生成森林，如下圖所示，基于鄰接表存盤的深度優先生成樹是不唯一的 ，

二、廣度優先遍歷

廣度優先遍歷(Breadth First Search)，又稱為廣度優先搜索，簡稱BFS，

1、BFS演算法

如果說圖的深度優先遍歷類似樹的前序遍歷，那么圖的廣度優先遍歷就類似于樹的層序遍歷了，
廣度優先搜索是一種分層的查找程序，每向前走一步可能訪問一批頂點，不像深度優先搜索那樣有往回退的情況，因此它不是一個遞回的演算法，為了實作逐層的訪問，演算法必須借助一個輔助佇列，以記憶正在訪問的頂點的下一層頂點，
以下是廣度優先遍歷的代碼：

/*鄰接矩陣的廣度遍歷演算法*/
void BFSTraverse(MGraph G){
	int i, j;
	Queue Q;
	for(i = 0; i<G,numVertexes; i++){
		visited[i] = FALSE;
	}
	InitQueue(&Q);	//初始化一輔助用的佇列
	for(i=0; i<G.numVertexes; i++){
		//若是未訪問過就處理
		if(!visited[i]){
			vivited[i] = TRUE;	//設定當前訪問過
			visit(i);	//訪問頂點
			EnQueue(&Q, i);	//將此頂點入佇列
			//若當前佇列不為空
			while(!QueueEmpty(Q)){
				DeQueue(&Q, &i);	//頂點i出佇列
				//FirstNeighbor(G,v):求圖G中頂點v的第一個鄰接點，若有則回傳頂點號，否則回傳-1，
				//NextNeighbor(G,v,w):假設圖G中頂點w是頂點v的一個鄰接點，回傳除w外頂點v
				for(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){
					//檢驗i的所有鄰接點
					if(!visited[j]){
						visit(j);	//訪問頂點j
						visited[j] = TRUE;	//訪問標記
						EnQueue(Q, j);	//頂點j入佇列
					}
				}
			}
		}
	}
}

以下面這個無向圖為例

其廣度優先遍歷的結果為 a b c d e f g h abcdefgh abcdefgh，

2、BFS演算法性能分析

無論是鄰接表還是鄰接矩陣的存盤方式，BFS 演算法都需要借助一個輔助佇列Q, n個頂點均需入隊一次，在最壞的情況下，空間復雜度為 O ( V ) O(V) O(V)，
采用鄰接表存盤方式時，每個頂點均需搜索一次(或入隊一次)， 在搜索任一頂點的鄰接點時，每條邊至少訪問一次，演算法總的時間復雜度為 O ( V + E ) O(V + E) O(V+E)，采用鄰接矩陣存盤方式時，查找每個頂點的鄰接點所需的時間為 O ( V ) O(V) O(V)，故演算法總的時間復雜度為 O ( V 2 ) O(V^2) O(V2)，

注意：圖的鄰接矩陣表示是唯一的，但對于鄰接表來說，若邊的輸入次序不同，生成的鄰接表也不同，因此，對于同樣一個圖，基于鄰接矩陣的遍歷所得到的DFS序列和BFS序列是唯一的，基于鄰接表的遍歷所得到的DFS序列和BFS序列是不唯一的，

三、圖的遍歷與圖的連通性

圖的遍歷演算法可以用來判斷圖的連通性，
對于無向圖來說，若無向圖是連通的，則從任一結點出發， 僅需一次遍歷就能夠訪問圖中的所有頂點；若無向圖是非連通的，則從某一個頂點出發，一次遍歷只能訪問到該頂點所在連通分量的所有頂點，而對于圖中其他連通分量的頂點，則無法通過這次遍歷訪問，對于有向圖來說，若從初始點到圖中的每個頂點都有路徑，則能夠訪問到圖中的所有頂點，否則不能訪問到所有頂點，
故在BFSTraverse ()或DFSTraverse ()中添加了第二個for回圈，再選取初始點，繼續進行遍歷，以防止一次無法遍歷圖的所有頂點，對于無向圖，上述兩個函式呼叫BFS (G,i)或DFS(G,i)的次數等于該圖的連通分量數；而對于有向圖則不是這樣，因為一個連通的有向圖分為強連通的和非強連通的，它的連通子圖也分為強連通分量和非強連通分量，非強連通分量一次呼叫BFS (G, i)或DFS (G, i)無法訪問到該連通分量的所有頂點，
如下圖所示為有向圖的非強連通分量，

最小生成樹

一個連通圖的生成樹是一個極小的連通子圖，它含有圖中全部的頂點，但只有足以構成一棵樹的 n ? 1 n-1 n?1條邊，若砍去它的一條邊，則會使生成樹變成非連通圖；若給它增加一條邊，則會形成圖中的一潭訓路，對于一個帶權連通無向圖 G = ( V , E ) G=(V, E) G=(V,E)，生成樹不同，其中邊的權值之和最小的那棵生成樹（構造連通網的最小代價生成樹），稱為G的最小生成樹(Minimum-Spanning-Tree, MST)，

構造最小生成樹有多種演算法，但大多數演算法都利用了最小生成樹的下列性質：假設 G = ( V , E ) G=(V, E) G=(V,E)是一個帶權連通無向圖， U U U是頂點集 V V V的一個非空子集，若 ( u , v ) (u,v) (u,v)是一條具有最小權值的邊，其中 u ∈ U , v ∈ V ? U u∈U,v∈V-U u∈U,v∈V?U，則必存在一棵包含邊 ( u , v ) (u, v) (u,v)的最小生成樹，
基于該性質的最小生成樹演算法主要有Prim演算法和Kruskal演算法，它們都基于貪心演算法的策略，
下面介紹一個通用的最小生成樹演算法：

GENERIC_MST(G){
	T=NULL;
	while T 未形成一棵生成樹;
		do 找到一條最小代價邊(u, v)并且加入T后不會產生回路;
			T=T U (u, v);
}

通用演算法每次加入一條邊以逐漸形成一棵生成樹，下面介紹兩種實作上述通用演算法的途徑，

一、普里姆（Prim）演算法

Prim演算法構造最小生成樹的程序如下圖所示，初始時從圖中任取一頂點(如頂點加入樹T，此時樹中只含有一個頂點，之后選擇一個與當前T中頂點集合距離最近的頂點，并將該頂點和相應的邊加入T，每次操作后T中的頂點數和邊數都增1，以此類推，直至圖中所有的頂點都并入T，得到的T就是最小生成樹，此時T中必然有n-1條邊，
通俗點說就是：從一個頂點出發，在保證不形成回路的前提下，每找到并添加一條最短的邊，就把當前形成的連通分量當做一個整體或者一個點看待，然后重復“找最短的邊并添加”的操作，

Prim演算法的步驟如下：
假設 G = { V , E } G= \{V, E\} G={V,E}是連通圖，其最小生成樹 T = ( U , E T ) T=(U, E_T) T=(U,ET?)， E T E_T ET?是最小生成樹中邊的集合，
初始化：向空樹 T = ( U , E T ) T=(U, E_T) T=(U,ET?)中添加圖 G = ( V , E ) G=(V, E) G=(V,E)的任一頂點 u 0 u_0 u0?，使 U = { u 0 } U=\{u_0\} U={u0?}， E T = N U L L E_T=NULL ET?=NULL，
回圈(重復下列操作直至 U = V U=V U=V)：從圖 G G G中選擇滿足 { ( u , v ) ∣ u ∈ U , v ∈ V ? U } \{(u, v)|u∈U, v∈V-U\} {(u,v)∣u∈U,v∈V?U}且具有最小權值的邊 ( u , v ) (u,v) (u,v),加入樹 T T T，置 U = U ∪ { v } U=U∪\{v\} U=U∪{v}， E T = E T U { ( u , v ) } E_T= E_TU\{(u, v)\} ET?=ET?U{(u,v)}，

額，不得不說這樣理解起來有點抽象，為了能描述這個演算法，我們先構造一個鄰接矩陣，如下圖的右圖所示，

于是普里姆(Prim) 演算法代碼如下，左側數字為行號，其中INFINITY為權值極大值，不妨設65535，MAXVEX 為頂點個數最大值，此處大于等于9即可，

/*Prim演算法生成最小生成樹*/
void MiniSpanTree_Prim(G){
	int min, i, j, k;
	int adjvex[MAXVEX];	//保存相關頂點下標
	int lowcost[MAXVEX];	//保存相關頂點間邊的權值
	lowcost[0] = 0;	//初始化第一個權值為0，即v0加入生成樹
	//lowcost的值為0，在這里就是此下標的頂點已經加入生成樹
	adjvex[0] = 0;	//初始化第一個頂點下標為0
	for(i=1; i<G.numVertexes; i++){
		lowcost[i] = G.arc[0][i];	//將v0頂點與之組成邊的權值存入陣列
		adjvex[i] = 0;	//初始化都為v0的下標
	}
	for(i=1; i<G.numVertexes; i++){
		min = INFINITY;	//初始化最下權值為∞，通常設定一個不可能的很大的數字
		j = 1; k = 0;
		//回圈全部頂點
		while(j < G.numVertexes){
			//如果權值不為0且權值小于min
			if(lowcost[j] != 0 && lowcost[j] < min){
				min = lowcost[j];	//則讓當前權值成為最小值
				k = j;	//將當前最小值的下標存入k
			}
			j++;
		}
		print("(%d, %d)", adjvex[k], k);	//列印當前頂點邊中權值的最小邊
		for(j=1; j<G.numvertexes; j++){
			//若下標為k頂點各邊權值小于此前這些頂點未被加入生成樹權值
			if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){
				lowcost[j] = G.arc[k][j];	//將較小權值存入lowcost
				adjvex[j] = k;	//將下標為k的頂點存入adjvex
			}
		}
	}
}

由演算法代碼中的回圈嵌套可得知此演算法的時間復雜度為 O ( n 2 ) O(n^2) O(n2)，

二、克魯斯卡爾（Kruskal）演算法

與Prim演算法從頂點開始擴展最小生成樹不同，Kruskal 演算法是一種按權值的遞增次序選擇合適的邊來構造最小生成樹的方法，

Kruskal演算法構造最小生成樹的程序如下圖所示，初始時為只有n個頂點而無邊的非連通圖 T = V , T= {V, {}} T=V,，每個頂點自成一個連通分量，然后按照邊的權值由小到大的順序，不斷選取當前未被選取過且權值最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入 T T T，否則舍棄此邊而選擇下一條權值最小的邊，以此類推，直至 T T T中所有頂點都在一個連通分量上，

演算法思路：
我們可以直接就以邊為目標去構建，因為權值是在邊上，直接去找最小權值的邊來構建生成樹也是很自然的想法，只不過構建時要考慮是否會形成環路而已，此時我們就用到了圖的存盤結構中的邊集陣列結構，以下是edge邊集陣列結構的定義代碼：

/*對邊集陣列Edge結構的定義*/
typedef struct{
	int begin;
	int end;
	int weight;
}Edge;

我們將下面左圖的鄰接矩陣通程序式轉化為右圖的邊集陣列，并且對它們按權值從小到大排序，

于是Kruskal演算法代碼如下，左側數字為行號，其中MAXEDGE為邊數量的極大值，此處大于等于15即可，MAXVEX為頂點個數最大值，此處大于等于9即可，

/*Kruskar演算法生成最小生成樹*/
void MiniSpanTree_Kruskal(MGraph G){
	int i, n, m;
	Edge edges[MAXEDGE];	//定義邊集陣列
	int parent[MAXVEX];	//定義一陣列用來判斷邊與邊是否形成環路
	/*此處省略將鄰接矩陣G轉化為邊集陣列edges并按照權由小到大排序的代碼*/
	for(i=0; i<G.numVertexes; i++){
		parent[i] = 0;	//初始化陣列為0
	}
	for(i=0; i<G.numVertexes; i++){
		n = Find(parent, edges[i].begin);
		m = Find(parent, edge[i],end);
		/*假如n與m不等，說明此邊沒有與現有生成樹形成環路*/
		if(n != m){
		/*將此邊的結尾頂點放入下標為起點的parent中
		表示此頂點已經在生成樹集合中*/
		parent[n] = m;
		printf("(%d, %d)", edges[i].begin, 
						edges[i].end, edges[i].weight);
		}
	}
}

/*查找連線頂點的尾部下標*/
int Find(int *parent, int f){
	while(parent[f] > 0){
		f = parent[f];
	}
	return f;
}

此演算法的Find函式由邊數e決定，時間復雜度為 O ( l o g e ) O(loge) O(loge)，而外面有一個for回圈e次，所以克魯斯卡爾演算法的時間復雜度為 O ( e l o g e ) O(eloge) O(eloge)，
對比兩個演算法，克魯斯卡爾演算法主要是針對邊來展開，邊數少時效率會非常高，所以對于稀疏圖有很大的優勢；而普里姆演算法對于稠密圖，即邊數非常多的情況會更好一些，

最短路徑

在網圖和非網圖中，最短路徑的含義是不同的，由于非網圖它沒有邊上的權值，所謂的最短路徑，其實就是指兩頂點之間經過的邊數最少的路徑；而對于網圖來說，最短路徑，是指兩頂點之間經過的邊上權值之和最少的路徑，并且我們稱路徑上的第一個頂點是源點，最后一個頂點是終點，

一、迪杰斯特拉( Dijkstra )演算法

Dijkstra演算法用于構建單源點的最短路徑—，即圖中某個點到任何其他點的距離都是最短的，例如，構建地圖應用時查找自己的坐標離某個地標的最短距離，可以用于有向圖，但是不能存在負權值，

我們以上圖為例，通俗點說，這個迪杰斯特拉(Dijkstra) 演算法，它并不是一下子求出了 v 0 v_0 v0?到 v 8 v_8 v8?的最短路徑，而是一步步求出它們之間頂點的最短路徑，程序中都是基于已經求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得到你要的結果，

Dijkstra演算法設定一個集合S記錄已求得的最短路徑的頂點，
在構造的程序中還設定了個輔助陣列:
dist[]：記錄從源點 v 0 v_0 v0?到其他各頂點當前的最短路徑長度，它的初態為：若從 v 0 v_0 v0?到 v i v_i vi?;有弧，則dist[i]為弧上的權值；否則置dist[i]為 ∞ ∞ ∞，

例如，對圖6.17中的圖應用 Dijkstra演算法求從頂點1出發至其余頂點的最短路徑的程序，如表6.1所示，演算法執行程序的說明如下，

• 初始化：集合S初始為 v 1 {v_1} v1?， v 1 v_1 v1?可達 v 2 v_2 v2?和 v 5 v_5 v5?， v 1 v_1 v1?不可達 v 3 v_3 v3?和 v 4 v_4 v4?，因此dist[]陣列各元素的初值依次設定為dist[2]=10，dist[3]= ∞ ∞ ∞，dist[4]= ∞ ∞ ∞，dist[5]=5，
• 第一輪：選出最小值dist[5]，將頂點 v 5 v_5 v5?并入集合 S S S,即此時已找到 v 1 v_1 v1?到 ν 5 ν_5 ν5?的最短路徑，當 v 5 v_5 v5?加入 S S S后，從 v 1 v_1 v1?到集合 S S S中可達頂點的最短路徑長度可能會產生變化，因此需要更新dist[]陣列， v 5 v_5 v5?可達 v 2 v_2 v2?，因 v 1 → v 5 → v 2 v_1→v_5→v_2 v1?→v5?→v2?的距離8比dist[2]=10小，更新dist[2]=8； v 5 v_5 v5?可達 v 3 v_3 v3?， v 1 → v 5 → v 3 v_1→v_5→v_3 v1?→v5?→v3?的距離14，更新dist[3]=14； v 5 v_5 v5?可達 v 4 v_4 v4?， v 1 → v 5 → v 4 v_1→v_5→v_4 v1?→v5?→v4?的距離7，更新dist[4]=7，
• 第二輪：選出最小值dist[4]，將頂點 ν 4 ν_4 ν4?并入集合 S S S，繼續更新dist[]陣列， ν 4 ν_4 ν4?不可達 v 2 v_2 v2?，dist[2]不變； v 4 v_4 v4?可達 v 3 v_3 v3?， v 1 → v 5 → v 4 → v 3 v_1→v_5→v_4→v_3 v1?→v5?→v4?→v3?的距離13比dist[3]小，故更新dist[3]=13，
• 笫三輪：選出最小值dist[2]，將頂點 ν 2 ν_2 ν2?并入集合 S S S，繼續更新dist[]陣列， v 2 v_2 v2?可達 ν 3 ν_3 ν3?， v 1 → v 5 → v 2 → v 3 v_1→v_5→v_2→v_3 v1?→v5?→v2?→v3?的距離9比dist[3]小，更新dist[3]=9，
• 第四輪：選出唯一最小值dist[3]，將頂點 v 3 v_3 v3?并入集合 S S S，此時全部頂點都已包含在 S S S中，

顯然，Dijkstra 演算法也是基于貪心策略的，使用鄰接矩陣或者帶權的鄰接表表示時，時間復雜度為 O ( V 2 ) O(V^2) O(V2)，
人們可能只希望找到從源點到某個特定頂點的最短路徑，但這個問題和求解源點到其他所有頂點的最短路徑一樣復雜，時間復雜度也為 O ( V 2 ) O(V^2) O(V2)，

二、弗洛伊德( Floyd )演算法

定義一個n階方陣序列 A ( ? 1 ) , A ( 0 ) , . . . , A ( n ? 1 ) A^{(-1)},A^{(0)},...,A^{(n-1)} A(?1),A(0),...,A(n?1)，其中， A ( ? 1 ) [ i ] [ j ] = a r c s [ i ] [ j ] A^{(-1)}[i][j] = arcs[i][j] A(?1)[i][j]=arcs[i][j] A ( k ) [ i ] [ j ] = M i n { A ( k ? 1 ) [ i ] [ j ] , A ( k ? 1 ) [ i ] [ k ] + A ( k ? 1 ) [ k ] [ j ] , k = 0 , 1 , . . . , n ? 1 } A^{(k)}[i][j] = Min\{A^{(k-1)}[i][j],A^{(k-1)}[i][k]+A^{(k-1)}[k][j],k=0,1,...,n-1\} A(k)[i][j]=Min{A(k?1)[i][j],A(k?1)[i][k]+A(k?1)[k][j],k=0,1,...,n?1}式中， A ( 0 ) [ i ] [ j ] A^{(0)}[i][j] A(0)[i][j]是從頂點 v i v_i vi?到 v j v_j vj?、中間頂點的序號不大于k的最短路徑的長度，Floyd演算法是一個迭代的程序，每迭代一次，在從 v i v_i vi?到 v j v_j vj?的最短路徑上就多考慮了一個頂點；經過 n n n次迭代后，所得到的 A ( n ? 1 ) [ i ] [ j ] A^{(n-1)}[i][j] A(n?1)[i][j]就是 v i v_i vi?到 v j v_j vj?的最短路徑長度，即方陣 A ( n ? 1 ) A^{(n-1)} A(n?1)中就保存了任意一對頂點之間的最短路徑長度，

上圖所示為帶權有向圖 G G G及其鄰接矩陣，演算法執行程序的說明如下，

• 初始化：方陣 A ( ? 1 ) [ i ] [ j ] = a r c s [ i ] [ j ] A^{(-1)}[i][j] = arcs[i][j] A(?1)[i][j]=arcs[i][j]，
• 第一輪：將 v 0 v_0 v0?作為中間頂點，對于所有頂點 { i , j } \{i, j\} {i,j}，如果有 A ? 1 [ i ] [ j ] > A ? 1 [ i ] [ 0 ] + A ? 1 [ 0 ] [ j ] A^{-1}[i][j] > A^{-1}[i][0] + A^{-1}[0][j] A?1[i][j]>A?1[i][0]+A?1[0][j]，則將 A ? 1 [ i ] [ j ] A^{-1}[i][j] A?1[i][j]更新為 A ? 1 [ i ] [ 0 ] + A ? 1 [ 0 ] [ j ] A^{-1}[i][0] + A^{-1}[0][j] A?1[i][0]+A?1[0][j]，有 A ? 1 [ 2 ] [ 1 ] > A ? 1 [ 2 ] [ 0 ] + A ? 1 [ 0 ] [ 1 ] = 11 A^{-1}[2][1] > A^{-1}[2][0] + A^{-1}[0][1] = 11 A?1[2][1]>A?1[2][0]+A?1[0][1]=11，更新 A ? 1 [ 2 ] [ 1 ] = 11 A^{-1}[2][1] = 11 A?1[2][1]=11，更新后的方陣標記為 A 0 A^0 A0，
• 第二輪：將 v 1 v_1 v1?作為中間頂點，繼續監測全部頂點對 { i , j } \{i, j\} {i,j}，有 A 0 [ 0 ] [ 2 ] > A 0 [ 0 ] [ 1 ] + A 0 [ 1 ] [ 2 ] = 10 A^{0}[0][2] > A^{0}[0][1] + A^{0}[1][2] = 10 A0[0][2]>A0[0][1]+A0[1][2]=10，更新后的方陣標記為 A 1 A^1 A1，
• 第三輪：將 v 2 v_2 v2?作為中間頂點，繼續監測全部頂點對 { i , j } \{i, j\} {i,j}，有 A 1 [ 1 ] [ 0 ] > A 1 [ 1 ] [ 2 ] + A 1 [ 2 ] [ 0 ] = 9 A^{1}[1][0] > A^{1}[1][2] + A^{1}[2][0] = 9 A1[1][0]>A1[1][2]+A1[2][0]=9，更新后的方陣標記為 A 2 A^2 A2，此時 A 2 A^2 A2中保存的就是任意頂點對的最短路徑長度，

應用Floyd演算法求所有頂點之間的最短路徑長度的程序如下表所示，

從這個表中，可以發下一些規律：

可以看出，矩陣中，每一步中紅線劃掉的部分都不用考慮計算，只需要計算紅線外的部分，節省了計算量，

Floyd演算法的時間復雜度為 O ( V 3 ) O(V^3) O(V3)，不過由于其代碼很緊湊，且并不包含 其他復雜的資料結構，因此隱含的常數系數是很小的，即使對于中等規模的輸入來說，它仍然是相當有效的，
Floyd演算法允許圖中有帶負權值的邊，但不允許有包含帶負權值的邊組成的回路，Floyd 演算法同樣適用于帶權無向圖，因為帶權無向圖可視為權值相同往返二重邊的有向圖，
也可以用單源最短路徑演算法來解決每對頂點之間的最短路徑問題，輪流將每個頂點作為源點，并且在所有邊權值均非負時，運行一次 Dijkstra演算法，其時間復雜度為 O ( V 3 ) ? V = O ( V 3 ) O(V^3)*V = O(V^3) O(V3)?V=O(V3)，

---

拓撲排序

一、定義

在一個表示工程的有向圖中，用頂點表示活動，用弧表示活動之間的優先關系，這樣的有向圖為頂點表示活動的網，我們稱為AOV網( Activity On VertexNetwork)，
若用DAG圖表示一個工程，其頂點表示活動，用有向邊 < V i , V j > <V_i, V_j> <Vi?,Vj?>表示活動 V i V_i Vi?必須先于活動 V j V_j Vj?進行的這樣一種關系，在AOV網中，活動 V i V_i Vi?是活動 V j V_j Vj?的直接前驅，活動 V j V_j Vj?是活動 V i V_i Vi?的直接后繼，這種前驅和后繼關系具有傳遞性，且任何活動 V i V_i Vi?不能以它自己作為自己的前驅或后繼，
設 G = ( V , E ) G=(V,E) G=(V,E)是一個具有n個頂點的有向圖， V V V中的頂點序列 V 1 , V 2 , . . . V n V_1, V_2, ... V_n V1?,V2?,...Vn?，滿足若從頂點 V i V_i Vi?到 V j V_j Vj?有一條路徑，則在頂點序列中頂點 V i V_i Vi?必在頂點 V j V_j Vj?之前，則我們稱這樣的頂點序列為一個拓撲序列，

所謂拓撲排序，其實就是對一個有向圖構造拓撲序列的程序，每個AOV網都有一個或多個拓撲排序序列，

二、演算法

對一個AOV網進行拓撲排序的演算法有很多，下面介紹比較常用的一種方法的步驟:

• ①從AOV網中選擇一個沒有前驅的頂點并輸出，
• ②從網中洗掉該頂點和所有以它為起點的有向邊，
• ③重復①和②直到當前的AOV網為慷訓當前網中不存在無前驅的頂點為止，如果輸出頂點數少了，哪怕是少了一個，也說明這個網存在環(回路)，不是AOV網，

上圖所示為拓撲排序程序的示例，每一輪選擇一個入度為0的頂點并輸出，然后洗掉該頂點和所有以它為起點的有向邊，最后得到拓撲排序的結果為 { 1 , 2 , 4 , 3 , 5 } \{1,2, 4, 3,5\} {1,2,4,3,5}，
拓撲排序演算法的實作如下：

bool TopologicalSort(Graph G){
	InitStack(S);	//初始化堆疊，存盤入度為0的頂點
	for(int i=0; i<G.vexnum; i++){
		if(indegree[i] == 0){
			Push(S, i);	//將所有入度為0的頂點進堆疊
		}
	}
	int count = 0;	//計數，記錄當前已經輸出的頂點數
	while(!IsEmpty(S)){	//堆疊不空，則存在入度為0的頂點
		Pop(S, i);	//頂點元素出堆疊
		printf("%d ", i);	//輸出頂點i
		count++;
		for(p=G.vertices[i].finstarc; p; p=p->nextarc){
			//將所有i指向的頂點的入度減1，并且將入度減為0的頂點壓入堆疊S
			v = p->adjvex;
			if(!--indegree[v]){
				Push(S, v);	//入度為0，則入堆疊
			}
		}
	}
	if(count < G.vexnum){
		return false;	//輸出頂點少了，有向圖中有回路，排序失敗
	}else{
		return true;	//拓撲排序成功
	}
}

由于輸出每個頂點的同時還要洗掉以它為起點的邊，故拓撲排序的時間復雜度為 O ( V + E ) O(V+E) O(V+E)，
此外，利用深度優先遍歷也可實作拓撲排序，

用拓撲排序演算法處理AOV網時，應注意以下問題:
①入度為零的頂點，即沒有前驅活動的或前驅活動都已經完成的頂點，工程可以從這個頂點所代表的活動開始或繼續，
②若一個頂點有多個直接后繼，則拓撲排序的結果通常不唯一；但若各個頂點已經排在一個線性有序的序列中，每個頂點有唯一的前驅后繼關系，則拓撲排序的結果是唯一的，
③由于AOV網中各頂點的地位平等，每個頂點編號是人為的，因此可以按拓撲排序的結果重新編號，生成AOV網的新的鄰接存盤矩陣，這種鄰接矩陣可以是三角矩陣；但對于一般的圖來說，若其鄰接矩陣是三角矩陣，則存在拓撲序列；反之則不一定成立，

---

關鍵路徑

一、定義

拓撲排序主要是為解決一個工程能否順序進行的問題，但有時我們還需要解決工程完成需要的最短時間問題，
在帶權有向圖中，以頂點表示事件，以有向邊表示活動，以邊上的權值表示完成該活動的開銷(如完成活動所需的時間)，稱之為用邊表示活動的網路，簡稱AOE網，AOE網和AOV網都是有向無環圖，不同之處在于它們的邊和頂點所代表的含義是不同的，AOE網中的邊有權值；而AOV網中的邊無權值，僅表示頂點之間的前后關系，
AOE網具有以下兩個性質：

• ①只有在某頂點所代表的事件發生后，從該頂點出發的各有向邊所代表的活動才能開始；
• ②只有在進入某頂點的各有向邊所代表的活動都已結束時，該頂點所代表的事件才能發生，

如上圖的AOE網，在AOE網中僅有一個入度為0的頂點，稱為開始頂點(源點)，它表示整個工程的開始；網中也僅存在一個出度為0的頂點，稱為結束頂點(匯點)，它表示整個工程的結束，我們把路徑上各個活動所持續的時間之和稱為路徑長度，從源點到匯點具有最大長度的路徑叫關鍵路徑，在關鍵路徑上的活動叫關鍵活動，
完成整個工程的最短時間就是關鍵路徑的長度，即關鍵路徑上各活動花費開銷的總和，這是因為關鍵活動影響了整個工程的時間，即若關鍵活動不能按時完成，則整個工程的完成時間就會延長，因此，只要找到了關鍵活動，就找到了關鍵路徑，也就可以得出最短完成時間，

二、演算法

在分析演算法之前，需要了解幾個重要的引數：

1.事件的最早發生時間 v e ve ve：即頂點 V k V_k Vk?的最早發生時期，
2.事件的最晚發生時間 v l vl vl：即頂點 V k V_k Vk?的最晚發生時間，也就是每個頂點對應的事件最晚需要開始的時間，超出此時間將會延誤整個工期，
3.活動的最早開始時間 e e e：即弧 a i a_i ai?的最早發生時間，
4.活動的最晚開始時間 l l l：即弧 a i a_i ai?的最晚發生時間，也就是不推遲工期的最晚開工時間，
5.一個活動 a i a_i ai?的最遲開始時間 l ( i ) l(i) l(i)和其最早開始時間 e ( i ) e(i) e(i)的差額 d ( i ) = l ( i ) ? e ( i ) d(i) =l(i)- e(i) d(i)=l(i)?e(i)：它是指該活動完成的時間余量，即在不增加完成整個工程所需總時間的情況下，活動 a i a_i ai?可以拖延的時間，若一個活動的時間余量為零，則說明該活動必須要如期完成，否則就會拖延整個工程的進度，所以稱 l ( i ) ? e ( i ) = 0 l(i)- e(i) = 0 l(i)?e(i)=0即 l ( i ) = e ( i ) l(i)=e(i) l(i)=e(i)的活動 a i a_i ai?是關鍵活動，

求關鍵路徑的演算法步驟如下:

1. 從源點出發，令 v e ( 源 點 ) = 0 ve(源點)=0 ve(源點)=0， 按拓撲排序求其余頂點的最早發生時間 v e ( ) ve() ve()，
2. 從匯點出發，令 v l ( 匯 點 ) = v e ( 匯 點 ) vl(匯點)= ve(匯點) vl(匯點)=ve(匯點)，按逆拓撲排序求其余頂點的最遲發生時間 v l ( ) vl() vl()，
3. 根據各頂點的 v e ( ) ve() ve()值求所有弧的最早開始時間 e ( ) e() e()，
4. 根據各頂點的 v l ( ) vl() vl()值求所有弧的最遲開始時間 l ( ) l() l()，
5. 求AOE網中所有活動的差額 d ( ) d() d()， 找出所有 d ( ) = 0 d()=0 d()=0的活動構成關鍵路徑，

上圖所示為求解關鍵路徑的程序，簡單說明如下:

1. 求 v e ( ) ve() ve()：初始 v e ( 1 ) = 0 ve(1)=0 ve(1)=0，在拓撲排序輸出頂點的程序中，求得 v e ( 2 ) = 3 ve(2)=3 ve(2)=3， v e ( 3 ) = 2 ve(3)=2 ve(3)=2， v e ( 4 ) = m a x { v e ( 2 ) + 2 , v e ( 3 ) + 4 } = m a x { 5 , 6 } = 6 ve(4)=max\{ve(2)+2, ve(3)+4\} = max\{5, 6\} = 6 ve(4)=max{ve(2)+2,ve(3)+4}=max{5,6}=6， v e ( 5 ) = 6 ve(5) = 6 ve(5)=6， v e ( 6 ) = m a x { v e ( 5 ) + 1 , v e ( 4 ) + 0 , v e ( 3 ) + 3 } = m a x { 7 , 8 , 5 } = 8 ve(6) = max\{ve(5)+1, ve(4)+0, ve(3)+3\} = max\{7, 8, 5\} = 8 ve(6)=max{ve(5)+1,ve(4)+0,ve(3)+3}=max{7,8,5}=8，
2. 求 v l ( ) vl() vl()：初始 v l ( 6 ) = 8 vl(6)=8 vl(6)=8，在逆拓撲排序出堆疊程序之中，求得 v l ( 5 ) = 7 vl(5)=7 vl(5)=7， v l ( 4 ) = 6 vl(4)=6 vl(4)=6， v l ( 3 ) = m i n { v l ( 4 ) ? 4 , v l ( 6 ) ? 3 } = m i n { 2 , 5 } = 2 vl(3)=min\{vl(4)-4, vl(6)-3\} = min\{2, 5\}=2 vl(3)=min{vl(4)?4,vl(6)?3}=min{2,5}=2， v l ( 2 ) = m i n { v l ( 5 ) ? 3 , v l ( 4 ) ? 2 } = m i n { 4 , 4 } = 4 vl(2)=min\{vl(5)-3,vl(4)-2\}=min\{4,4\}=4 vl(2)=min{vl(5)?3,vl(4)?2}=min{4,4}=4， v l ( 1 ) vl(1) vl(1)必然為 0 0 0而無需再求，
3. 弧的最早開始時間 e ( ) e() e()等于該弧的起點的頂點的 v e ( ) ve() ve()，求得結果如上表所示，
4. 弧的最遲開始時間 l ( i ) l(i) l(i)等于該弧的終點的頂點的 v l ( ) vl() vl()減去該弧持續的時間，求得結果如上表所示，
5. 根據 l ( i ) ? e ( i ) = 0 l(i)-e(i)=0 l(i)?e(i)=0的關鍵活動，得到的關鍵路徑為 ( v 1 , v 3 , v 4 , v 6 ) (v_1,v_3,v_4,v_6) (v1?,v3?,v4?,v6?)，

對于關鍵路徑，需要注意以下幾點:
①關鍵路徑上的所有活動都是關鍵活動，它是決定整個工程的關鍵因素，因此可通過加快關鍵活動來縮短整個工程的工期，但也不能任意縮短關鍵活動，因為一旦縮短到一定的程度，該關鍵活動就可能會變成非關鍵活動，
②網中的關鍵路徑并不唯一，
且對于有幾條關鍵路徑的網，只提高一條關鍵路徑上的關鍵活動速度并不能縮短整個工程的工期，只有加快那些包括在所有關鍵路徑上的關鍵活動才能達到縮短工期的目的，

總結

圖是計算機科學中非常常用的一類資料結構，同時也是最復雜的資料結構了，對它的學習，涉及到順序表、鏈表、堆疊、佇列、樹等之前學的幾乎所有資料結構，所以學習圖之前要對這幾種資料結構都要有所了解才行，

---

附錄

上文鏈接

資料結構：樹

下文鏈接

資料結構：查找（待更新）

參考資料

1、程杰：《大話資料結構》
2、嚴蔚敏、吳偉民：《資料結構（C語言版）》
3、王道論壇：《資料結構考研復習指導》