本章主要介紹圖的存儲方法、圖的遍歷方式、無向圖的連通分量分解問題、拓撲排序、最短路徑問題、最小生成樹。

圖的相關(guān)概念

簡單路徑：路徑上所有頂點都是互異的，但是第一個和最后一個頂點可以相同也可以不同。

有向圖的環(huán)：第一個和最后一個頂點相同且長至少為1的路徑。

簡單環(huán)：是簡單路徑的環(huán)。

無環(huán)圖：沒有環(huán)的有向圖或無向圖。

有向無環(huán)圖簡稱為DAG（Directed Acyclic Graph）。

連通圖：無向圖中從每一個頂點到每個其他頂點都存在一條路徑，稱其為連通圖。

強連通圖：有向圖中從每一個頂點到每個其他頂點都存在一條路徑，稱其為強連通圖。

圖的存儲方法

①鄰接矩陣

鄰接矩陣用一個二維數(shù)組G來表示圖，對無權(quán)圖，若邊(u,v)存在，則G[u][v]=true，否則G[u][v]=false。對于有權(quán)圖，若存在邊(u,v)且邊(v,w)上的權(quán)值為w，則G[u][v]=w，否則G[u][v]=∞（實際編碼中∞可以用圖中不可能出現(xiàn)的權(quán)值來表示）。其缺點是空間需求太大，若為稀疏圖會浪費大量空間。因此只有當圖中頂點數(shù)量在103數(shù)量級及以下時，才適合使用鄰接矩陣。

②鄰接表

對每個頂點，使用一個表來存放該頂點所有相鄰的頂點，通常用vector來實現(xiàn)這樣的表，此時的空間復(fù)雜度就會降低到O(|E|+|V|)。

對于無權(quán)圖，由于只需要存儲頂點所有相鄰的頂點編號，因此鄰接表內(nèi)的元素類型可以直接定義為int類型，則整個圖可以定義為：vector<vector<int>>graph(MAX);

若需要存儲邊權(quán)或其他信息，可以定義一個新的edge類存放這些信息，并把鄰接表內(nèi)的元素類型定義為edge類型：

那么需要添加邊時，如向graph中添加權(quán)值為6的邊(2,3)，代碼可以這樣寫：

一般情況下都會使用鄰接表存儲圖。

圖的遍歷

分為深度優(yōu)先遍歷（DFS）和廣度優(yōu)先遍歷（BFS）。

①深度優(yōu)先遍歷DFS

圖的深度優(yōu)先類似于樹的深度優(yōu)先遍歷，但需要注意圖中可能是有環(huán)的，因此需要一個訪問數(shù)組記錄頂點是否被訪問，以免頂點重復(fù)訪問。

②廣度優(yōu)先遍歷BFS

和樹的廣度優(yōu)先遍歷一樣，圖的BFS也需要一個隊列。同樣，因為可能有環(huán)，所以也需要一個訪問數(shù)組記錄是否入過隊列，以免頂點重復(fù)入隊，即重復(fù)訪問。

無向圖的連通分量分解問題

若無向圖是不連通的，那么這個圖一定可以分解為多個連通子圖，稱這些連通子圖為原圖的連通分量。分解無向圖的連通分量，通常有兩種方法：深度（廣度）優(yōu)先遍歷和并查集。?

※ 在該問題中DFS更容易實現(xiàn)也更常用；并查集的實現(xiàn)方法則更為直觀、便于編寫代碼。

拓撲排序

拓撲排序的算法是每次找出任意一個入度為0的頂點，將該頂點加入拓撲序列中，并將它及其邊一起從圖中刪除，重復(fù)這一操作，直至所有頂點都被加入拓撲序列中。若剩余的頂點入度均不為0，則說明此時這些頂點間形成了環(huán)。因此，拓撲排序還可以用于判斷圖中是否有環(huán)。

?

最短路徑問題

最短路徑問題可以分為單源最短路徑問題和每對頂點間最短路徑問題。

對不同的圖的最短路徑問題的求解算法如圖13.1：

①BFS算法（針對無權(quán)圖的單源最短路徑算法）

無權(quán)圖中沒有邊權(quán)，因此路徑長度即為路徑上邊的數(shù)量，也可以認為所有邊的邊權(quán)為1。則出發(fā)點到達其他頂點的最短路徑長度恰好是該頂點所處的層號。

②Dijkstra算法（針對正權(quán)圖的單源最短路徑算法）

是典型的貪心算法。該算法常用一個dis數(shù)組記錄從源點到所有頂點的最短路徑長度。

最小生成樹

在無向連通圖中找到n-1條邊，使得無向圖仍保持連通。若使得邊的權(quán)值最小的生成樹就是最小生成樹。求解最小生成樹的算法一般有2種：Prim算法和Kruskal算法。 此處只介紹Kruskal算法，因為其思想和代碼實現(xiàn)都較為簡單。Kruskal算法中需要使用并查集，初始狀態(tài)下，Kruskal算法不考慮所有的邊，每個頂點自成一個集合。

它的執(zhí)行步驟是：1）先將所有的邊權(quán)從小到大排序；2）遍歷所有的邊，假設(shè)當前訪問的兩個端點為u和v，如果u和v沒有在一個集合中，就將該邊作為最小生成樹的一條邊，并將u和v所在的集合合并成一個集合；如果u和v本身就在同一個集合，則忽略這條邊。若執(zhí)行算法時，發(fā)現(xiàn)最小生成樹的邊少于n-1條，說明原圖不連通。