一、前言

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

圖論涉及相當(dāng)多的算法，包括圖DFS和BFS、連通性、拓撲排序、最小生成樹、最短路徑、最大流網(wǎng)絡(luò)、圖的著色問題等等

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

二、圖的定義

圖（graph）

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

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

需要注意的是在圖論中邊表示的是頂點之間的邏輯關(guān)系，粗細長短都無所謂的。包括上面的頂點也一樣，表示邏輯事物或?qū)ο?，畫的時候大小形狀都無所謂。

頂點（vertex）的屬性：

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

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

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

一條邊是一個頂點對(u,v)，u, v ∈ V，按照圖的頂點對是否有序，頂點對有序的圖稱為有向圖（directed graph, digraph，此時邊(u,v)和(v,u)是兩條不同的邊，頂點對無序的圖稱為無向圖（undirected graph），此時邊(u,v)和(v,u)是兩條相同的邊，無向圖可看作一個特殊的有向圖。

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

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

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

平行邊： 兩個頂點之間存在多條邊相連接。

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

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

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

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

稀疏圖：有很少條邊或?。ㄟ叺臈l數(shù)|E|遠小于|V|²）的圖稱為稀疏圖（sparse graph）。

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

三、圖的儲存

那么，該怎么去儲存圖呢？

1.鄰接矩陣

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

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

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

需要注意的是，有向圖與無向圖的矩陣不同，對于無向圖，當(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來快速地將一個數(shù)組中的所有元素都初始化為0。

上面的代碼等價于：

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

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

cin>>n>>m;//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;    //無向邊：
}

2.鄰接表

又叫鏈?zhǔn)角跋蛐?，其實就是鏈表。鄰接表的思想是，對于圖中的每一個頂點，用一個數(shù)組來記錄這個點和哪些點相連。

如果用鄰接矩陣表示稀疏圖就會浪費大量內(nèi)存空間，而用鏈接表，則是通過把頂點所能到的頂點的邊保存在鏈表中來表示圖。

步驟

1.用 h 數(shù)組保存各個節(jié)點能到的第一個節(jié)點的編號。開始時，h[i] 全部為 -1。

2.用 e 數(shù)組保存節(jié)點編號，ne 數(shù)組保存 e 數(shù)組對應(yīng)位置的下一個節(jié)點所在的索引。

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

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

模板如下：

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

3.鄰接矩陣與鄰接表的優(yōu)缺點對比

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

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

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

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

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

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

到此這篇關(guān)于C++詳細講解圖論的基礎(chǔ)與圖的儲存的文章就介紹到這了,更多相關(guān)C++圖論內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論