① 數據結構——圖
轉自： http://www.cnblogs.com/mcgrady/archive/2013/09/23/3335847.html
閱讀目錄
一，圖的定義
二，圖相關的概念和術語
三，圖的創建和遍歷
四，最小生成樹和最短路徑
五，演算法實現
這一篇我們要總結的是圖(Graph)，圖可能比我們之前學習的線性結構和樹形結構都要復雜，不過沒有關系，我們一點一點地來總結，那麼關於圖我想從以下幾點進行總結：
1，圖的定義？
2，圖相關的概念和術語？
3，圖的創建和遍歷？
4，最小生成樹和最短路徑？
5，演算法實現？
一，圖的定義
什麼是圖呢？
圖是一種復雜的非線性結構。
在線性結構中，數據元素之間滿足唯一的線性關系，每個數據元素(除第一個和最後一個外)只有一個直接前趨和一個直接後繼；
在樹形結構中，數據元素之間有著明顯的層次關系，並且每個數據元素只與上一層中的一個元素(雙親節點)及下一層的多個元素(孩子節點)相關；
而在圖形結構中，節點之間的關系是任意的，圖中任意兩個數據元素之間都有可能相關。
圖G由兩個集合V(頂點Vertex)和E(邊Edge)組成，定義為G=(V，E)
二，圖相關的概念和術語
1，無向圖和有向圖
對於一個圖，若每條邊都是沒有方向的，則稱該圖為無向圖。圖示如下：
因此，(Vi，Vj)和(Vj，Vi)表示的是同一條邊。注意，無向圖是用小括弧，而下面介紹的有向圖是用尖括弧。
無向圖的頂點集和邊集分別表示為：
V(G)={V1，V2，V3，V4，V5}
E(G)={(V1，V2)，(V1，V4)，(V2，V3)，(V2，V5)，(V3，V4)，(V3，V5)，(V4，V5)}
對於一個圖G，若每條邊都是有方向的，則稱該圖為有向圖。圖示如下。
因此，和是兩條不同的有向邊。注意，有向邊又稱為弧。
有向圖的頂點集和邊集分別表示為：
V(G)={V1，V2，V3}
E(G)={，，，}
2，無向完全圖和有向完全圖
我們將具有n(n-1)/2條邊的無向圖稱為無向完全圖。同理，將具有n(n-1)條邊的有向圖稱為有向完全圖。
3，頂點的度
對於無向圖，頂點的度表示以該頂點作為一個端點的邊的數目。比如，圖(a)無向圖中頂點V3的度D(V3)=3
對於有向圖，頂點的度分為入度和出度。入度表示以該頂點為終點的入邊數目，出度是以該頂點為起點的出邊數目，該頂點的度等於其入度和出度之和。比如，頂點V1的入度ID(V1)=1，出度OD(V1)=2，所以D(V1)=ID(V1)+OD(V1)=1+2=3
記住，不管是無向圖還是有向圖，頂點數n，邊數e和頂點的度數有如下關系：
因此，就拿有向圖(b)來舉例，由公式可以得到圖G的邊數e=(D(V1)+D(V2)+D(V3))/2=(3+2+3)/2=4
4，子圖
故名思義，這個就不解釋了。
5，路徑，路徑長度和迴路
路徑，比如在無向圖G中，存在一個頂點序列Vp,Vi1,Vi2,Vi3…，Vim，Vq，使得(Vp,Vi1)，(Vi1,Vi2)，…,(Vim,Vq)均屬於邊集E(G)，則稱頂點Vp到Vq存在一條路徑。
路徑長度，是指一條路徑上經過的邊的數量。
迴路，指一條路徑的起點和終點為同一個頂點。
6，連通圖(無向圖)
連通圖是指圖G中任意兩個頂點Vi和Vj都連通，則稱為連通圖。比如圖(b)就是連通圖。下面是一個非連通圖的例子。
上圖中，因為V5和V6是單獨的，所以是非連通圖。
7，強連通圖(有向圖)
強連通圖是對於有向圖而言的，與無向圖的連通圖類似。
8，網
帶」權值」的連通圖稱為網。如圖所示。
三，圖的創建和遍歷
1，圖的兩種存儲結構
1) 鄰接矩陣，原理就是用兩個數組，一個數組保存頂點集，一個數組保存邊集。下面的演算法實現里邊我們也是採用這種存儲結構。如下圖所示：
2) 鄰接表，鄰接表是圖的一種鏈式存儲結構。這種存儲結構類似於樹的孩子鏈表。對於圖G中每個頂點Vi，把所有鄰接於Vi的頂點Vj鏈成一個單鏈表，這個單鏈表稱為頂點Vi的鄰接表。
2，圖的兩種遍歷方法
1) 深度優先搜索遍歷
深度優先搜索DFS遍歷類似於樹的前序遍歷。其基本思路是：
a) 假設初始狀態是圖中所有頂點都未曾訪問過，則可從圖G中任意一頂點v為初始出發點，首先訪問出發點v，並將其標記為已訪問過。
b) 然後依次從v出發搜索v的每個鄰接點w，若w未曾訪問過，則以w作為新的出發點出發，繼續進行深度優先遍歷，直到圖中所有和v有路徑相通的頂點都被訪問到。
c) 若此時圖中仍有頂點未被訪問，則另選一個未曾訪問的頂點作為起點，重復上述步驟，直到圖中所有頂點都被訪問到為止。
圖示如下：
註：紅色數字代表遍歷的先後順序，所以圖(e)無向圖的深度優先遍歷的頂點訪問序列為：V0，V1，V2，V5，V4，V6，V3，V7，V8
如果採用鄰接矩陣存儲，則時間復雜度為O(n2)；當採用鄰接表時時間復雜度為O(n+e)。
2) 廣度優先搜索遍歷
廣度優先搜索遍歷BFS類似於樹的按層次遍歷。其基本思路是：
a) 首先訪問出發點Vi
b) 接著依次訪問Vi的所有未被訪問過的鄰接點Vi1，Vi2，Vi3，…，Vit並均標記為已訪問過。
c) 然後再按照Vi1，Vi2，… ，Vit的次序，訪問每一個頂點的所有未曾訪問過的頂點並均標記為已訪問過，依此類推，直到圖中所有和初始出發點Vi有路徑相通的頂點都被訪問過為止。
圖示如下：
因此，圖(f)採用廣義優先搜索遍歷以V0為出發點的頂點序列為：V0，V1，V3，V4，V2，V6，V8，V5，V7
如果採用鄰接矩陣存儲，則時間復雜度為O(n2)，若採用鄰接表，則時間復雜度為O(n+e)。
四，最小生成樹和最短路徑
1，最小生成樹
什麼是最小生成樹呢？在弄清什麼是最小生成樹之前，我們需要弄清什麼是生成樹？
用一句語簡單概括生成樹就是：生成樹是將圖中所有頂點以最少的邊連通的子圖。
比如圖(g)可以同時得到兩個生成樹圖(h)和圖(i)
知道了什麼是生成樹之後，我們就很容易理解什麼是最小生成樹了。所謂最小生成樹，用一句話總結就是：權值和最小的生成樹就是最小生成樹。
比如上圖中的兩個生成樹，生成樹1和生成樹2，生成樹1的權值和為：12，生成樹2的權值為：14，我們可以證明圖(h)生成樹1就是圖(g)的最小生成樹。
那麼如何構造最小生成樹呢？可以使用普里姆演算法。
2，最短路徑
求最短路徑也就是求最短路徑長度。下面是一個帶權值的有向圖，表格中分別列出了頂點V1其它各頂點的最短路徑長度。
表：頂點V1到其它各頂點的最短路徑表
從圖中可以看出，頂點V1到V4的路徑有3條(V1，V2，V4)，(V1，V4)，(V1，V3，V2，V4)，其路徑長度分別為15，20和10，因此，V1到V4的最短路徑為(V1，V3，V2，V4)。
那麼如何求帶權有向圖的最短路徑長度呢？可以使用迪傑斯特拉(Dijkstra)演算法。