內(nèi)容整理于魚c工作室教程
1. 圖的基本概念
1.1 圖的概念
圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G(V,E)，其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合。
1.2 圖的基本概念
頂點: 線性表中我們把數(shù)據(jù)元素叫元素，樹中叫結(jié)點，在圖中數(shù)據(jù)元素我們則稱之為頂點(Vertex)。線性表可以沒有數(shù)據(jù)元素，稱為空表，樹中可以沒有結(jié)點，叫做空樹，而圖結(jié)構(gòu)在咱國內(nèi)大部分的教材中強調(diào)頂點集合V要有窮非空。
線性表中，相鄰的數(shù)據(jù)元素之間具有線性關(guān)系，樹結(jié)構(gòu)中，相鄰兩層的結(jié)點具有層次關(guān)系，而圖結(jié)構(gòu)中，任意兩個頂點之間都可能有關(guān)系，頂點之間的邏輯關(guān)系用邊來表示，邊集可以是空的。
無向邊：若頂點Vi到Vj之間的邊沒有方向，則稱這條邊為無向邊(Edge)，用無序偶(Vi,Vj)來表示。
有向邊：若從頂點Vi到Vj的邊有方向，則稱這條邊為有向邊，也成為弧(Arc)，用有序偶來表示，Vi稱為弧尾，Vj稱為弧頭。
上圖G2是一個有向圖，G2={V2,E2}，其中V2={A,B,C,D}，E2={<B,A>,<B,C>,<C,A>,<A,D>}
簡單圖：在圖結(jié)構(gòu)中，若不存在頂點到其自身的邊，且同一條邊不重復出現(xiàn)，則稱這樣的圖為簡單圖。
無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。含有n個頂點的無向完全圖有n*(n-1)/2條邊。
有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖。含有n個頂點的有向完全圖有n*(n-1)條邊。
稀疏圖和稠密圖：這里的稀疏和稠密是模糊的概念，都是相對而言的，通常認為邊或弧數(shù)小于n*logn（n是頂點的個數(shù)）的圖稱為稀疏圖，反之稱為稠密圖。
有些圖的邊或弧帶有與它相關(guān)的數(shù)字，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)(Weight)，帶權(quán)的圖通常稱為網(wǎng)(Network)。
假設(shè)有兩個圖G1=(V1,E1)和G2=(V2,E2)，如果V2?V1，E2?E1，則稱G2為G1的子圖(Subgraph)。
圖的頂點與邊之間的關(guān)系：
(1) 無向圖的頂點與邊之間的關(guān)系：
對于無向圖G=(V,E)，如果邊(V1,V2)∈E，則稱頂點V1和V2互為鄰接點(Adjacent)，即V1和V2相鄰接。
邊(V1,V2)依附(incident)于頂點V1和V2，或者說邊(V1,V2)與頂點V1和V2相關(guān)聯(lián)。
頂點V的度(Degree)是和V相關(guān)聯(lián)的邊的數(shù)目，記為TD(V)，如下圖，頂點A與B互為鄰接點，邊(A,B)依附于頂點A與B上，頂點A的度為3。
(2) 有向圖的頂點與邊之間的關(guān)系：
對于有向圖G=(V,E)，如果有∈E，則稱頂點V1鄰接到頂點V2，頂點V2鄰接自頂點V1。
以頂點V為頭的弧的數(shù)目稱為V的入度(InDegree)，記為ID(V)，以V為尾的弧的數(shù)目稱為V的出度(OutDegree)，記為OD(V)，因此頂點V的度為TD(V)=ID(V)+OD(V)。
下圖頂點A的入度是2，出度是1，所以頂點A的度是3。
簡單路徑：序列中頂點不重復出現(xiàn)的路徑稱為簡單路徑，除了第一個頂點和最后一個頂點之外，其余頂點不重復出現(xiàn)的回路，稱為簡單回路或簡單環(huán)。
下圖左側(cè)是簡單環(huán)，右側(cè)不是簡單環(huán)：
連通圖：在無向圖G中，如果從頂點V1到頂點V2有路徑，則稱V1和V2是連通的，如果對于圖中任意兩個頂點Vi和Vj都是連通的，則稱G是連通圖(ConnectedGraph)。
下圖左側(cè)不是連通圖，右側(cè)是連通圖：
1.3 圖的存儲結(jié)構(gòu)
圖的存儲結(jié)構(gòu)相比較線性表與樹來說就復雜很多。我們回顧下，對于線性表來說，是一對一的關(guān)系，所以用數(shù)組或者鏈表均可簡單存放。樹結(jié)構(gòu)是一對多的關(guān)系，所以我們要將數(shù)組和鏈表的特性結(jié)合在一起才能更好的存放。那么我們的圖，是多對多的情況，另外圖上的任何一個頂點都可以被看作是第一個頂點，任一頂點的鄰接點之間也不存在次序關(guān)系。
因為任意兩個頂點之間都可能存在聯(lián)系，因此無法以數(shù)據(jù)元素在內(nèi)存中的物理位置來表示元素之間的關(guān)系（內(nèi)存物理位置是線性的，圖的元素關(guān)系是平面的）。如果用多重鏈表來描述倒是可以做到，但在幾節(jié)課前的樹章節(jié)我們已經(jīng)討論過，純粹用多重鏈表導致的浪費是無法想像的（如果各個頂點的度數(shù)相差太大，就會造成巨大的浪費）。
1.3.1 鄰接矩陣
（無向圖）
考慮到圖是由頂點和邊或弧兩部分組成，合在一起比較困難，那就很自然地考慮到分為兩個結(jié)構(gòu)來分別存儲。頂點因為不區(qū)分大小、主次，所以用一個一維數(shù)組來存儲是狠不錯的選擇。而邊或弧由于是頂點與頂點之間的關(guān)系，一維數(shù)組肯定就搞不定了，那我們不妨考慮用一個二維數(shù)組來存儲。
圖的鄰接矩陣(Adjacency Matrix)存儲方式是用兩個數(shù)組來表示圖。一個一維數(shù)組存儲圖中頂點信息，一個二維數(shù)組(稱為鄰接矩陣)存儲圖中的邊或弧的信息。
我們可以設(shè)置兩個數(shù)組，頂點數(shù)組為vertex[4]={V0,V1,V2,V3}，邊數(shù)組arc[4][4]為對稱矩陣(0表示不存在頂點間的邊，1表示頂點間存在邊)。
對稱矩陣：所謂對稱矩陣就是n階矩陣的元滿足a[i][j]=a[j][i](0<=i,j<=n)。即從矩陣的左上角到右下角的主對角線為軸，右上角的元與左下角相對應的元全都是相等的。
有了這個二維數(shù)組組成的對稱矩陣，我們就可以很容易地知道圖中的信息：
要判定任意兩頂點是否有邊無邊就非常容易了；
要知道某個頂點的度，其實就是這個頂點Vi在鄰接矩陣中第i行(或第i列)的元素之和；
求頂點Vi的所有鄰接點就是將矩陣中第i行元素掃描一遍，arc[i][j]為1就是鄰接點咯。
（有向圖）
無向圖的邊構(gòu)成了一個對稱矩陣，貌似浪費了一半的空間，那如果是有向圖來存放，會不會把資源都利用得很好呢？
可見頂點數(shù)組vertex[4]={V0,V1,V2,V3}，弧數(shù)組arc[4][4]也是一個矩陣，但因為是有向圖，所以這個矩陣并不對稱，例如由V1到V0有弧，得到arc[1][0]=1，而V0到V1沒有弧，因此arc[0][1]=0。
另外有向圖是有講究的，要考慮入度和出度，頂點V1的入度為1，正好是第V1列的各數(shù)之和，頂點V1的出度為2，正好是第V1行的各數(shù)之和。
（網(wǎng)）
在圖的術(shù)語中，我們提到了網(wǎng)這個概念，事實上也就是每條邊上帶有權(quán)的圖就叫網(wǎng)。
1.3.2 鄰接表
（無向圖）
鄰接矩陣看上去是個不錯的選擇，首先是容易理解，第二是索引和編排都很舒服~
但是我們也發(fā)現(xiàn)，對于邊數(shù)相對頂點較少的圖，這種結(jié)構(gòu)無疑是存在對存儲空間的極大浪費。
因此我們可以考慮另外一種存儲結(jié)構(gòu)方式，例如把數(shù)組與鏈表結(jié)合一起來存儲，這種方式在圖結(jié)構(gòu)也適用，我們稱為鄰接表(AdjacencyList)。
鄰接表的處理方法是這樣：
圖中頂點用一個一維數(shù)組存儲，當然，頂點也可以用單鏈表來存儲，不過數(shù)組可以較容易地讀取頂點信息，更加方便。圖中每個頂點Vi的所有鄰接點構(gòu)成一個線性表，由于鄰接點的個數(shù)不確定，所以我們選擇用單鏈表來存儲。
（有向圖）
若是有向圖，鄰接表結(jié)構(gòu)也是類似的，我們先來看下把頂點當弧尾建立的鄰接表，這樣很容易就可以得到每個頂點的出度：
（網(wǎng)）
對于帶權(quán)值的網(wǎng)圖，可以在邊表結(jié)點定義中再增加一個數(shù)據(jù)域來存儲權(quán)值即可：
1.3.3 十字鏈表
鄰接表固然優(yōu)秀，但也有不足，例如對有向圖的處理上，有時候需要再建立一個逆鄰接表~那我們思考了：有沒有可能把鄰接表和逆鄰接表結(jié)合起來呢？答案是肯定的，這就是我們現(xiàn)在要談的十字鏈表(Orthogonal List)。為此我們重新定義頂點表結(jié)點結(jié)構(gòu)：
1.3.4 鄰接多重表
講了有向圖的優(yōu)化存儲結(jié)構(gòu)，對于無向圖的鄰接表，有沒有問題呢？如果我們在無向圖的應用中，關(guān)注的重點是頂點的話，那么鄰接表是不錯的選擇，但如果我們更關(guān)注的是邊的操作，比如對已經(jīng)訪問過的邊做標記，或者刪除某一條邊等操作，鄰接表就顯得不那么方便了。
到底有多煩？小甲魚用圖片告訴你：
若要刪除(V0,V2)這條邊，就需要對鄰接表結(jié)構(gòu)中邊表的兩個結(jié)點進行刪除操作。
1.3.5 邊集數(shù)組
邊集數(shù)組是由兩個一維數(shù)組構(gòu)成，一個是存儲頂點的信息，另一個是存儲邊的信息，這個邊數(shù)組每個數(shù)據(jù)元素由一條邊的起點下標(begin)、終點下標(end)和權(quán)(weight)組成。
1.4 圖的遍歷
樹的遍歷我們談了四種方式，大家回憶一下，樹因為根結(jié)點只有一個，并且所有的結(jié)點都只有一個雙親，所以不是很難理解。但是談到圖的遍歷，那就復雜多了，因為它的任一頂點都可以和其余的所有頂點相鄰接，因此極有可能存在重復走過某個頂點或漏了某個頂點的遍歷過程。對于圖的遍歷，如果要避免以上情況，那就需要科學地設(shè)計遍歷方案，通常有兩種遍歷次序方案：它們是深度優(yōu)先遍歷和廣度優(yōu)先遍歷。
1.4.1 深度優(yōu)先遍歷
深度優(yōu)先遍歷(DepthFirstSearch)，也有稱為深度優(yōu)先搜索，簡稱為DFS。
它的具體思想類似于課程開頭講的找鑰匙方案，無論從哪一間房間開始都可以，將房間內(nèi)的墻角、床頭柜、床上、床下、衣柜、電視柜等挨個尋找，做到不放過任何一個死角，當所有的抽屜、儲藏柜中全部都找遍，接著再尋找下一個房間。現(xiàn)在請大家一起來想辦法走以下這個迷宮：
我們可以約定右手原則：在沒有碰到重復頂點的情況下，分叉路口始終是向右手邊走，每路過一個頂點就做一個記號。迷宮走完了，所有的頂點也遍歷過了，這就是深度優(yōu)先遍歷！反應快的童鞋一定會感覺深度優(yōu)先遍歷其實就是一個遞歸的過程嘛~如果再細心觀察，你會發(fā)現(xiàn)整個遍歷過程就像是一棵樹的前序遍歷！
1.4.2 廣度優(yōu)先遍歷
廣度優(yōu)先遍歷（BreadthFirstSearch），又稱為廣度優(yōu)先搜索，簡稱BFS。
如果以之前我們找鑰匙的例子來講，運用深度優(yōu)先遍歷意味著要先徹底查找完一個房間再開始另一個房間的搜索。但我們知道，鑰匙放在沙發(fā)地下等犄角旮旯的可能性極低，因此我們運用新的方案：先看看鑰匙是否放在各個房間的顯眼位置，如果沒有，再看看各個房間的抽屜有沒有。這樣逐步擴大查找的范圍的方式我們稱為廣度優(yōu)先遍歷。
廣度優(yōu)先遍歷是連通圖的一種遍歷策略。其基本思想如下：
1、從圖中某個頂點V0出發(fā)，并訪問此頂點；
2、從V0出發(fā)，訪問V0的各個未曾訪問的鄰接點W1，W2，…,Wk;然后,依次從W1,W2,…,Wk出發(fā)訪問各自未被訪問的鄰接點；
3、重復步驟2，直到全部頂點都被訪問為止。
