一、前言

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

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

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

二、圖的定義

圖（graph）

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

上圖中黑色的帶數字的點就是頂點,可抽象成某個事物或對象。頂點之間的線就是邊，表示事物與事物之間的關系。

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

頂點（vertex）的屬性：

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

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

邊又稱為線（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。

自環邊: 一條邊的起點終點是一個點。

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

有權圖： 權值就是一條邊的長度或代價。

無權圖： 不是邊的權值為0，而是全都為1。

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

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

稀疏圖：有很少條邊或弧（邊的條數|E|遠小于|V|2）的圖稱為稀疏圖（sparse graph）。

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

三、圖的儲存

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

1.鄰接矩陣

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

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

一個點到自己的距離是0，到沒有直接邊連接的點的權值是無窮大

需要注意的是，有向圖與無向圖的矩陣不同，對于無向圖，當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 為數組第一維大小
    {
        for(int j =  1; j <= n2; j++)// n2 為數組第一維大小
        {
           g[i][j] = g[j][i] =  0 ;
        }
    }

也可以借助memset來快速地將一個數組中的所有元素都初始化為0。

上面的代碼等價于：

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

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

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

2.鄰接表

又叫鏈式前向星，其實就是鏈表。鄰接表的思想是，對于圖中的每一個頂點，用一個數組來記錄這個點和哪些點相連。

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

步驟

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

2.用 e 數組保存節點編號，ne 數組保存 e 數組對應位置的下一個節點所在的索引。

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

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

模板如下：

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

3.鄰接矩陣與鄰接表的優缺點對比

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

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

鄰接表可以記錄重復邊：如果兩個點之間有多條邊，用鄰接矩陣只能記錄一條，但是用鄰接表就能記錄多條。雖然重復的邊看起來是多余的，但在很多時候對解題來說是必要的。

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

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

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