一、前言

在算法中一般都需要把問(wèn)題抽象成圖論問(wèn)題然后用圖論的算法解決問(wèn)題。

圖論涉及相當(dāng)多的算法，包括圖DFS和BFS、連通性、拓?fù)渑判颉⒆钚∩蓸?shù)、最短路徑、最大流網(wǎng)絡(luò)、圖的著色問(wèn)題等等

圖論算法在計(jì)算機(jī)科學(xué)中扮演著很重要的角色，它提供了對(duì)很多問(wèn)題都有效的一種簡(jiǎn)單而系統(tǒng)的建模方式。很多問(wèn)題都可以轉(zhuǎn)化為圖論問(wèn)題，然后用圖論的基本算法加以解決。

二、圖的定義

圖（graph）

如上圖是一個(gè)圖G，一個(gè)圖由頂點(diǎn)（vertex）集V和邊（edge）集E組成，即G=(V, E)，和樹(shù)類似，其頂點(diǎn)又稱為結(jié)點(diǎn)，并且邊是有意義的，如上圖(0,1)稱為一條邊。

上圖中黑色的帶數(shù)字的點(diǎn)就是頂點(diǎn),可抽象成某個(gè)事物或?qū)ο蟆ｍ旤c(diǎn)之間的線就是邊，表示事物與事物之間的關(guān)系。

需要注意的是在圖論中邊表示的是頂點(diǎn)之間的邏輯關(guān)系，粗細(xì)長(zhǎng)短都無(wú)所謂的。包括上面的頂點(diǎn)也一樣，表示邏輯事物或?qū)ο螅?huà)的時(shí)候大小形狀都無(wú)所謂。

頂點(diǎn)（vertex）的屬性：

度數(shù)（degree），與該頂點(diǎn)相關(guān)聯(lián)的總邊數(shù)，一個(gè)圖G的總度數(shù)d(V)等于總邊數(shù)2倍：2E。當(dāng)圖的邊具有方向時(shí)，一個(gè)頂點(diǎn)又分為出度（out-degree）和入度（in-degree），出度是以該頂點(diǎn)為起點(diǎn)的邊數(shù)，入度是以該頂點(diǎn)為終點(diǎn)的邊數(shù)。

階數(shù)（order），圖G中頂點(diǎn)集V的大小為G的階數(shù)。

邊又稱為線（line）或弧（arc），邊(u,v)中表示u和v鄰接（adjacent），(u, v) ∈ E，邊（edge）的屬性：

一條邊是一個(gè)頂點(diǎn)對(duì)(u,v)，u, v ∈ V，按照?qǐng)D的頂點(diǎn)對(duì)是否有序，頂點(diǎn)對(duì)有序的圖稱為有向圖（directed graph, digraph，此時(shí)邊(u,v)和(v,u)是兩條不同的邊，頂點(diǎn)對(duì)無(wú)序的圖稱為無(wú)向圖（undirected graph），此時(shí)邊(u,v)和(v,u)是兩條相同的邊，無(wú)向圖可看作一個(gè)特殊的有向圖。

有向邊： 有向邊就是固定這一條邊只能從x通往y，y通往x則不可以。

無(wú)向邊 : 無(wú)向邊就是一條邊可以從x通往y，y也可以通往x。

自環(huán)邊: 一條邊的起點(diǎn)終點(diǎn)是一個(gè)點(diǎn)。

平行邊： 兩個(gè)頂點(diǎn)之間存在多條邊相連接。

有權(quán)圖： 權(quán)值就是一條邊的長(zhǎng)度或代價(jià)。

無(wú)權(quán)圖： 不是邊的權(quán)值為0，而是全都為1。

稀疏圖: 每個(gè)頂點(diǎn)的度數(shù)較小的圖，如下圖：

稠密圖: 每個(gè)頂點(diǎn)的度數(shù)較大的圖，如下圖：

稀疏圖：有很少條邊或弧（邊的條數(shù)|E|遠(yuǎn)小于|V|2）的圖稱為稀疏圖（sparse graph）。

稠密圖：有很多條邊或弧 (邊的條數(shù)|E|接近|V|2) 的圖稱為稠密圖（dense graph）。 簡(jiǎn)單來(lái)說(shuō)：我們假設(shè)某個(gè)圖的點(diǎn)的個(gè)數(shù) 為 N, 邊的個(gè)數(shù)為 M， 當(dāng) M << N ^ 2 (平方)（當(dāng)邊數(shù)遠(yuǎn)小于點(diǎn)的平方）時(shí)稱為 稀疏圖，當(dāng) M ≈ N ^ 2 （當(dāng)邊數(shù)約等于點(diǎn)的平方）時(shí)稱為 稠密圖， 如果圖為稀疏圖的時(shí)候，我們一般用鄰接表儲(chǔ)存，稠密圖的時(shí)候，一般用鄰接矩陣存儲(chǔ)。

三、圖的儲(chǔ)存

那么，該怎么去儲(chǔ)存圖呢？

1.鄰接矩陣

鄰接矩陣是二維數(shù)據(jù) ：例如，g[ ][ ] 時(shí)空間需求為V^2,這種存儲(chǔ)方式適合存儲(chǔ)稠密圖

鄰接矩陣每一位存的是一條邊 行代表的是起始點(diǎn) ,列代表的是終止點(diǎn),而里面存的值就是這條邊的權(quán)值

一個(gè)點(diǎn)到自己的距離是0，到?jīng)]有直接邊連接的點(diǎn)的權(quán)值是無(wú)窮大

需要注意的是，有向圖與無(wú)向圖的矩陣不同，對(duì)于無(wú)向圖，當(dāng)vi、vj之間由邊，則a[i][j]=a[j][i]=1,但是有向圖，若i指向j,只有a[i][j]=1,a[j][i]=0

鄰接矩陣要初始化

如下：

for(int i = 1; i <= n1; i++)// n1 為數(shù)組第一維大小
    {
        for(int j =  1; j <= n2; j++)// n2 為數(shù)組第一維大小
        {
           g[i][j] = g[j][i] =  0 ;
        }
    }

也可以借助memset來(lái)快速地將一個(gè)數(shù)組中的所有元素都初始化為0。

上面的代碼等價(jià)于：

memset(g, 0, sizeof(g));

注意，memset只能用來(lái)初始化0和 -1，并且需要加上頭文件cstring。

cin>>n>>m;//n表示點(diǎn)的數(shù)量,m表示邊的數(shù)量
for(int i = 1;i <= m; i++){//枚舉輸入邊
    cin>>x>>y>>z;//如上描述
    dis[x][y] = z;    //有向邊：
    dis[x][y] = dis[y][x] = z;    //無(wú)向邊：
}

2.鄰接表

又叫鏈?zhǔn)角跋蛐牵鋵?shí)就是鏈表。鄰接表的思想是，對(duì)于圖中的每一個(gè)頂點(diǎn)，用一個(gè)數(shù)組來(lái)記錄這個(gè)點(diǎn)和哪些點(diǎn)相連。

如果用鄰接矩陣表示稀疏圖就會(huì)浪費(fèi)大量?jī)?nèi)存空間，而用鏈接表，則是通過(guò)把頂點(diǎn)所能到的頂點(diǎn)的邊保存在鏈表中來(lái)表示圖。

步驟

1.用 h 數(shù)組保存各個(gè)節(jié)點(diǎn)能到的第一個(gè)節(jié)點(diǎn)的編號(hào)。開(kāi)始時(shí)，h[i] 全部為 -1。

2.用 e 數(shù)組保存節(jié)點(diǎn)編號(hào)，ne 數(shù)組保存 e 數(shù)組對(duì)應(yīng)位置的下一個(gè)節(jié)點(diǎn)所在的索引。

3.用 idx 保存下一個(gè) e 數(shù)組中，可以放入節(jié)點(diǎn)位置的索引

4.插入邊使用的頭插法，例如插入：a->b。首先把b節(jié)點(diǎn)存入e數(shù)組，e[idx] = b。然后 b 節(jié)點(diǎn)的后繼是h[a]，ne[idx] = h[a]。最后，a 的后繼更新為 b 節(jié)點(diǎn)的編號(hào)，h[a] = idx，索引指向下一個(gè)可以存儲(chǔ)節(jié)點(diǎn)的位置，idx ++ 。

模板如下：

//鄰接表
const int N = 100010, M = N * 2;
//無(wú)向圖n條邊時(shí)，最多2n個(gè)idx，因?yàn)槊織l邊在鄰接表中會(huì)出現(xiàn)兩次
int h[N],  w[N], e[M], ne[M], idx;
//n個(gè)鏈表頭，e每一個(gè)結(jié)點(diǎn)的值，ne每一個(gè)結(jié)點(diǎn)的next指針
// 添加一條邊a->b
void add(int a, int b, int c)
{//e記錄當(dāng)前點(diǎn)的值(地址->值),ne下一點(diǎn)的地址(地址->地址)，h記錄指向的第一個(gè)點(diǎn)的地址(值->地址)
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);

3.鄰接矩陣與鄰接表的優(yōu)缺點(diǎn)對(duì)比

空間方面：當(dāng)圖的頂點(diǎn)數(shù)很多、但是邊的數(shù)量很少時(shí)，如果用鄰接矩陣，我們就需要開(kāi)一個(gè)很大的二維數(shù)組，最后我們需要存儲(chǔ) n*n 個(gè)數(shù)。但是用鄰接表，最后我們存儲(chǔ)的數(shù)據(jù)量只是邊數(shù)的兩倍。

效率方面：用鄰接表存圖的最大缺點(diǎn)就是隨機(jī)訪問(wèn)效率低。比如，我們需要詢問(wèn)點(diǎn) a 是否和點(diǎn) b 連，我們就要遍歷G[a]，檢查這個(gè)vector里是否有 b 。而在鄰接矩陣中，只需要根據(jù)G[a][b]就能判斷。

鄰接表可以記錄重復(fù)邊：如果兩個(gè)點(diǎn)之間有多條邊，用鄰接矩陣只能記錄一條，但是用鄰接表就能記錄多條。雖然重復(fù)的邊看起來(lái)是多余的，但在很多時(shí)候?qū)忸}來(lái)說(shuō)是必要的。

因此，我們需要對(duì)不同的應(yīng)用情景選擇不同的存圖方法。

如果是稀疏圖（頂點(diǎn)很多、邊很少），一般用鄰接表；

如果是稠密圖（頂點(diǎn)很少、邊很多），一般用鄰接矩陣。