本文包含了圖的基本概念

1.相關(guān)概念

1.1 無/有向

無向圖：每一個頂點之間的連線沒有方向

有向圖：連線有方向（類似離散數(shù)學(xué)的二元關(guān)系 <A,B>代表從A到B的邊，有方向）

<A,B>中A為始點，B為終點

在無向圖中，(V,U)和(U,V)是同一條邊

1.2 頂點和邊

圖中的節(jié)點叫做頂點。

頂點之間的線條就是邊，表示事物與事物之間的關(guān)系。

1.3 自回路/多重圖

1.4 完全圖

圖中每一個頂點都有連線（有最多的邊數(shù)）就叫做完全圖

設(shè)頂點為N個

• 無向完全圖中n(n-1)/2條邊
• 有向完全圖中n(n-1)條邊

1.5 鄰接與關(guān)聯(lián)

無向圖中(u,v)是一條邊

• 頂點u和v鄰接
• 邊(u,v)與頂點u和v相關(guān)聯(lián)

1.6 子圖

圖中G3是G1的子圖，G4是G2的子圖

簡單說來，就是子圖是原圖的一部分，包括頂點、邊（注意方向）都是原圖中的一部分

1.6 路徑

路徑是頂點序列

路徑是一個節(jié)點到另外一個節(jié)點需要經(jīng)過的邊

• 路徑長度：路徑上邊的數(shù)目
• 簡單路徑：除起點、終點可以相同外，路徑中其余頂點不相同
• 回路：起點和重點相同的簡單路徑

1.7 連通圖

兩個頂點之間只要有路徑，那就是連通的

• 連通圖：無向圖中任意兩點之間都有路徑，那么就是一個連通圖
• 連通分量：無向圖的極大連通子圖

注意，雖然連通分量被稱為“極大連通子圖”，但它并不是節(jié)點最多的哪一個。比如上圖中的G2和G3都是極大連通子圖。

---

• 強連通圖：有向圖中，如果兩個頂點之間U和V之間有U到V的路徑，那就一定有從V到U的路徑
• 強連通分量：有向圖的極大聯(lián)通子圖

強連通圖G1的極大強連通分量就是它自己（只有非強連通圖才有多個強連通分量）

上圖中G2就不是強聯(lián)通圖，因為4節(jié)點沒有入邊（也就沒有節(jié)點能到4）

• 第三圖的上半部分并非G1的強連通分量，但是是G2的強力連通分量。
• 同時，單獨的4頂點也是一個強連通分量（單獨頂點都是）

1.7 頂點的度

度：與該頂點相關(guān)聯(lián)的邊的數(shù)目

• 入度：射入v的邊的數(shù)目
• 出度：從v射出去的邊的數(shù)目

1.8 生成樹

生成樹包含圖中的所有頂點，但是只有足夠構(gòu)成一顆樹的n-1條邊

• 因為n-1條邊再加上一條就會構(gòu)成回路
• 生成樹中不包含回路

1.9 網(wǎng)

給圖中的每條邊都添加上權(quán)值，帶權(quán)的圖稱為網(wǎng)

2.表示法

2.1 鄰接矩陣

用二維數(shù)組來表示每個頂點之間的關(guān)系（矩陣）

優(yōu)缺點

優(yōu)點

• 便于判斷兩個頂點之間是否有邊，可以直接根據(jù)下標判斷，O(1)
• 便于計算各個頂點的度
  • 無向圖：第i行元素之和就是頂點i的度（前提是用1來表示）
  • 有向圖：第i行元素之和為頂點i的出度；第i列為入度

缺點

• 如果節(jié)點多，邊少，就會出現(xiàn)空間浪費
• 無法方便地找到一個頂點和那一條邊相連（需要遍歷）
• 對于無向圖，也會出現(xiàn)空間浪費

2.2 鄰接表

鄰接表有些類似于哈希表的拉鏈法。每一個節(jié)點后面跟著一個單鏈表，用于存儲與這個節(jié)點相連的節(jié)點。

在G2的有向圖中，一般存儲的是出度表，即從該節(jié)點出發(fā)的邊。如果邊有權(quán)值，則還需要存儲權(quán)值

優(yōu)缺點

優(yōu)點：

• 可以快速找到一個節(jié)點和誰相連（出度）

缺點

• 不便于判斷兩個頂點之間是否有邊
• 不便于計算有向圖各個頂點的度（需要遍歷所有節(jié)點）

關(guān)于第二個缺點，可以新增一個入度表（即一個出度表/一個入讀表）來計算。但是這樣會增加時空復(fù)雜度。

3.遍歷

3.1 深度優(yōu)先DFS

深度優(yōu)先以遞歸為基本思路，從一個結(jié)點開始，遞歸向后遍歷這個節(jié)點的單鏈表中的節(jié)點。

為了避免同一個節(jié)點遍歷多次，我們需要有一個bool數(shù)組來標識一個節(jié)點是否遍歷過。如果遍歷過，則把對應(yīng)下標的值設(shè)定為true來標識

由于深度優(yōu)先的遞歸部分只能遍歷連通圖。若出現(xiàn)了上圖中非聯(lián)通的情況，需要我們在外循環(huán)中重新遍歷一下bool標識數(shù)組，確認所有節(jié)點都遍歷完成。

如果漏了節(jié)點（就是沒有和其他節(jié)點聯(lián)通的獨立節(jié)點）那么就以此節(jié)點開頭再進行一次深度遍歷。

3.2 廣度優(yōu)先BFS

廣度優(yōu)先遍歷類似二叉樹的層序遍歷，依靠循環(huán)+隊列來完成遍歷

• 入起始節(jié)點，打印起始節(jié)點的值
• 出隊頭節(jié)點（第一次的時候是起始節(jié)點）往隊列中入該節(jié)點單鏈表中的所有節(jié)點
• 依此類推，出一個節(jié)點，就入這個節(jié)點單鏈表中的所有節(jié)點
• 同樣地用一個bool數(shù)組標識節(jié)點是否被訪問。如果被訪問了則跳過該節(jié)點
• 也需要在隊列循環(huán)結(jié)束后遍歷一遍bool數(shù)組，確認所有節(jié)點都訪問完畢。

3.3 判斷一個圖是否連通

使用任何遍歷方式，遍歷完畢后檢查bool數(shù)組

若有節(jié)點沒有被訪問，則說明是非連通圖

4.拓撲排序

https://blog.csdn.net/qq_43448856/article/details/119959241

給定一個圖，每次都選擇一個無入度（沒有入邊）的節(jié)點加入序列中，并刪除該節(jié)點的出邊

最終得到的序列就是一個拓撲排序之后的序列

• 每次刪除出邊后，都可能形成新的無入度的節(jié)點

因此，針對同一棵樹的拓撲排序序列，可能有多種不同的情況

5.最小生成樹算法

生成樹的概念參考 1.8 生成樹，最小生成樹即讓生成樹中所有邊的權(quán)值加起來最小

5.1 普里姆Prim

如圖中所示，我們先根據(jù)這個樹的結(jié)構(gòu)構(gòu)造三個數(shù)組

• nearest代表和這個節(jié)點最近的節(jié)點（默認為-1）
• lowcost代表和這個節(jié)點最近節(jié)點的權(quán)值（默認為無窮大）
• mark是一個bool數(shù)組，標識該節(jié)點是否已經(jīng)加入到最小生成樹

當(dāng)我們每從圖中取出一個節(jié)點的時候，就需要更新這三個表

如圖，當(dāng)我們?nèi)∽?之后，就需要更新和0連通的三個節(jié)點，其中nearest代表剛剛刪除掉的節(jié)點0，lowcost代表它們和0相連邊的權(quán)值；同時要把mark中0改為true，表明0已經(jīng)加入生成樹了

第二次選取的時候，遍歷lowcost表，找到權(quán)值最小的邊為(0,2)權(quán)值為1。此時就把2加入進去，并更新與2相連的節(jié)點3（注，必須要權(quán)值更小才需要更新）

依次遍歷，直到所有節(jié)點都加入了最小生成樹（左下角的圖）

該算法的時間復(fù)雜度為O(N^2)，只與節(jié)點的數(shù)量N有關(guān)

5.2 克魯斯卡爾Kruskal

構(gòu)建一個和原圖一樣的節(jié)點圖（無邊）在原圖中查找權(quán)值最小的邊，判斷其節(jié)點是否已經(jīng)相同，如果沒有形成環(huán)，則加入到最小生成樹的圖中

判斷是否成環(huán)可以通過并查集解決

如下圖，先遍歷所有邊，發(fā)現(xiàn)(0,2)的權(quán)值最小，判斷該邊加入后并不會使生成樹形成環(huán)，則加入該邊

• 下圖中(0,2)之間的邊1已經(jīng)移動到了T圖上
• 同時將0和2加入到同一個并查集的合集內(nèi)

同理繼續(xù)找權(quán)值最小的邊，加入到生成樹中。如下，將3邊移動到右圖。

此時我們遇到了3條權(quán)值最小的邊，權(quán)值都為5。此時可以隨便加入一條邊即可（不能使生成樹成環(huán)）

如下圖中(0,3)和(2,3)的邊加入后會使圖成環(huán)，不能選擇該邊

• 并查集中0、2、3、5已經(jīng)在一個集合中，此時判斷(0,3)在一個集合，該邊不能加入；(2,3)在一個集合中，該邊不能加入

應(yīng)該選擇(1,2)這條邊，其不會讓樹成環(huán)

此時所有邊都已經(jīng)連起來了，最小生成樹生成成功

算法分析

該算法的時間復(fù)雜度為O(E*logE)，其中E為邊的數(shù)目

6.最短路徑

帶權(quán)有向圖中，把一條路徑（僅考慮簡單路徑）上所經(jīng)邊的權(quán)值之和定義為該路徑的路徑長度

從源點到終點可能不止一條路徑，把路徑長度最短的那條路徑稱為最短路徑

6.1 單源最短路徑

思路有些類似并查集，path數(shù)組中存放的是每一個節(jié)點的上一條路徑，若下標1處存放0，則代表是從0走到1。同時d數(shù)組中標識從0走到下標1的長度。

把1加到s序列之后，發(fā)現(xiàn)0到節(jié)點2的路徑長度縮短了，從原本的(0,2)的6變成了現(xiàn)在(0,1)+(1,2)的4+1=5，長度縮短，對應(yīng)d數(shù)組中下標2處也需要更新

繼續(xù)下去，直到U數(shù)組中沒有節(jié)點，S數(shù)組中節(jié)點滿，即可獲得一個從0出發(fā)到任何節(jié)點的單源最短路徑

---

6.1.1 狄克斯特拉算法Dijkstra

求解單源最短路徑問題的算法

前提：給定一個帶權(quán)有向圖G和源點v，限定各邊上的權(quán)值大于等于0

基于定理：最短路徑上的頂點的最短路徑就是該路徑

理解：現(xiàn)有一條v到u的最短路徑v->……->a->u，那么v到a的最短路徑即為v->……->a

算法思路

把圖G中的頂點集合V分成兩部分：

第一部分，為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑v，……，u，就將u加入到集合S中，直到全部頂點都加入到S中，算法結(jié)束）

第二部分，為其余未求出最短路徑的頂點集合（用U表示）

過程：

1. 初始化：S只包含源點即S={v}，v的最短路徑為0。U包含除v以外的其他頂點，U中頂點i距離為邊上的權(quán)值（若v與i直接相連）或∞（v與i不是直接相連）

2. 從U中選取一個距離v最小的頂點u，把u加入S中（該選定的距離就是v到u的最短路徑長度）

3. 以u為新考慮的中間點，修改U中各頂點i的最短路徑長度

若從源點v到頂點 i的最短路徑長度（經(jīng)過頂點u）比原來最短路徑長度（不經(jīng)過頂點u）短，則修改頂點 i的最短路徑長度

4. 重復(fù)2、3步，直至所有頂點都包含在S中

代碼設(shè)計

著重解決兩個問題：

1. 如何存放最短路徑長度？

用一維數(shù)組d[i]存儲。源點v默認，d[i]表示源點到頂點i的最短路徑長度

如d[2]=12表示源點到頂點2的最短路徑長度為12

2. 如何存放最短路徑？

用一維數(shù)組path[]存儲。path數(shù)組中所存儲的數(shù)組代表當(dāng)前頂點在最短路徑中的前驅(qū)頂點

如path[3]=1，表示在最短路徑中，頂點3的前驅(qū)頂點是頂點1

算法演示

這是初始化狀態(tài)

發(fā)現(xiàn)數(shù)組d中頂點1距離源點距離最近，那么就將頂點1加入到S中

這時，我們需要更新剩余點的最短路徑長度和最短路徑

顯然，頂點2，3，4，5，6并不會都做更新。只有與頂點1直接相連的頂點才有可能會受影響。在上圖中會受影響的為頂點2和頂點4

原本頂點2的最短路徑長度是6，最短路徑是<0,2>?，F(xiàn)在由于頂點1的引入，最短路徑長度變?yōu)?，最短路徑變?yōu)?lt;0,1>,<1,2>

頂點4同理！

至此，就完成了一次頂點的引入。下面重復(fù)上述操作至所有頂點都在S中即可

下面是全過程：

總結(jié)一下：在更新d和path數(shù)組時，只有與本次引入S中的頂點i直接相連的后驅(qū)頂點才有可能發(fā)生改變，其余頂點是不可能變的

現(xiàn)在我們利用d和path數(shù)組來求解最短路徑長度和最短路徑：

• 求源點0到終點6的最短路徑長度

即為d[6]的值，為16

• 求0到6的最短路徑

從終點往源點找

時間復(fù)雜度

時間復(fù)雜度為 O(n²)