何為圖論

見名知意，圖論 (Graph Theory) 就是研究 圖 (Graph) 的數(shù)學(xué)理論和方法。圖是一種抽象的數(shù)據(jù)結(jié)構(gòu)，由 節(jié)點 (Node) 和 連接這些節(jié)點的 邊 (Edge) 組成。圖論在計算機科學(xué)、網(wǎng)絡(luò)分析、物流、社會網(wǎng)絡(luò)分析等領(lǐng)域有廣泛的應(yīng)用。

如下，這就是一個圖，可以看到這個圖有 $5$ 個頂點，分別編號為 { 0 , 1 , 2 , 3 , 4 } \{0, 1, 2, 3, 4\} {0,1,2,3,4}。同時這個圖有 $4$ 條邊，例如，在頂點 $2$ 和 頂點 $4$ 之間存在著一條邊。

圖的基本概念

在詳細講解圖論和有關(guān)圖論算法之前，先來了解一下在圖論中的一些基本表述和規(guī)范。

1. 圖 (Graph)：圖是一種由一組頂點和一組邊組成的數(shù)據(jù)結(jié)構(gòu)，記做 $G=(V,E)$，其中 $V$ 代表頂點集合，$E$? 代表邊集合。
2. 頂點 (Vertex)：頂點是圖的基本單位，也稱為節(jié)點。
3. 邊 (Edge)：一條邊是連接兩個頂點的線段或弧?？梢允菬o向的，也可以是有向的。一條邊可以記做為 $(u,v)$。在無向圖中，若存在一條$(u,v)$，表示可以從 $u$ 點直接走到 $v$ 點，反之亦然。但若在有向圖中，存在一條邊 $(u,v)$，表示可以從 $u$ 節(jié)點直接走向 $v$ 節(jié)點，如果不存在一條邊 $v,u$，那么 $v$ 節(jié)點就沒有辦法直接走向 $u$ 節(jié)點。
4. 無向圖 (Undirected Graph)：圖中的邊沒有方向，即 $(u,v)$ 和 $(v,u)$ 是同一條邊。
5. 有向圖 (Directed Graph/ Digraph)：圖中的邊有方向，即 $(u,v)$ 和 $(v,u)$? 不是同一條邊。
6. 簡單圖 (Simple Graph)：表示含有重邊（兩個頂點之間的多條邊）和自環(huán)（頂點到自身的邊）的圖。
7. 多重圖 (Multigraph)：允許有重邊和自環(huán)的圖。
8. 邊權(quán) (Weight of an Edge)：一般表示經(jīng)過這一條邊的代價（代價一般是由命題人定義的）。

如下圖，就是一個有向的簡單圖（通常來說，在有向圖中邊的方向用箭頭來表示）：

如下圖，就是一個無向的多重圖，其中存在兩條邊可以從頂點 $5$ 到頂點 $2$：

與此同時，為了方便起見，對于無向圖的處理，我們只需要在兩個頂點之間建立兩個方向相反的無向邊就可以表示一個無向圖，具體如下：

圖的表示方法

在計算機中，圖可以通過許多方式來構(gòu)建和表示?？偟目梢苑殖蓤D的鄰接矩陣和鄰接表兩種方法（關(guān)于鏈式前向星本文不過多展開敘述，有興趣的可以自行查閱相關(guān)文檔）。

圖的鄰接矩陣 (Adjacency Matrix)

若一個圖中有 $N$ 個頂點，那么我們就可以用一個 $N\times N$ 的矩陣來表示這個圖。我們一般定義，若矩陣的元素 $A_{i,j}\ne ?\infty$ 表示從節(jié)點 $i$ 到 $j$ 有一條有向邊，其中邊的權(quán)值為 $A_{i,j}$?。

假設(shè)存在一個有 $3$ 個頂點的圖，并且有三條有向邊 $E=\{(1,2),(2,3),(3,2)\}$，那么就可以用鄰接矩陣表示為：
$$G=\left[\begin{array}{cccc}& 1& 2& 3\\ 1& 0& 1& 0\\ 2& 0& 0& 1\\ 3& 0& 1& 0\end{array}\right]$$
畫成可視化的圖就長這個樣子：

在 C++ 中，我們可以簡單地用一個二維數(shù)組來表示：

// 定義一個矩陣。
int map[50][50];// 將所有的邊初始化為負無窮大。
for (int i=1; i<=50; i++)for (int j=1; j<=50; j++)map[i][j] = -0x7f7f7f7f;// 建邊，其中所有的邊權(quán)為1。
map[1][2] = map[2][3] = map[3][2] = 1;

圖的鄰接表 (Adjacency List)

鄰接表本質(zhì)上就是用鏈表表示圖。數(shù)組的每個元素表示一個頂點，元素的值是一個鏈表，鏈表中存儲該頂點的所有鄰接頂點。假設(shè)存在一個有 $4$ 個頂點的圖，并且有四條有向邊 $E=\{(1,2),(2,3),(3,2),(3,4)\}$，那么就可以用鄰接表表示為：

畫成可視化的圖就長這個樣子：

在 C++ 中，我們可以使用 STL模板庫 中的 vector 來實現(xiàn)：

#include <vector>
vector<int> G[50];  // 建圖。
G[1].push_back(2);
G[2].push_back(3);
G[3].push_back(2);
G[3].push_back(4);

一般情況下，推薦使用鄰接表的方式來存圖，因為使用鄰接矩陣比較浪費空間。在頂點數(shù)量非常多但邊非常少的圖中，$N^2$ 的時空復(fù)雜度會導(dǎo)致 MLE 或 TLE 等問題。

圖的各種性質(zhì)

1. 度數(shù) (Degree)：一個頂點的度是連接該頂點的邊的數(shù)量。在有向圖中，有 入度 (Indegree) 和 出度 (Outdegree) 之分（具體例子見后文）。
2. 路徑 (Path)：從一個頂點到另一個頂點的頂點序列，路徑上的邊沒有重復(fù)。
3. 回路 (Cycle)：起點和終點相同的路徑。
4. 連通圖 (Connected Graph)：任意兩個頂點之間都有路徑相連的無向圖。
5. 強連通圖 (Strongly Connected Graph)：任意兩個頂點之間都有路徑相連的有向圖。

對于下面這個無向圖不連通圖，頂點 $1$ 的度數(shù)為 $1$；頂點 $2$ 的度數(shù)為 $2$；頂點 $3$ 的度數(shù)為 $1$；頂點 $4$ 的度數(shù)為 $0$。同時，由于 $4$ 號頂點沒有度數(shù)，所以該頂點沒有辦法到達任何一個其他的頂點，所以這個圖是一個不連通圖：

如下圖，就是一個有向不強連通圖。其中，頂點 $1$ 的入度為 $0$，出度為 $2$；頂點 $2$ 的入度為 $1$，出度也為 $1$；頂點 $3$ 的入度為 $2$，但出度為 $0$。由于頂點 $1$ 和頂點 $2$ 可以走到頂點 $3$，但頂點 $3$ 沒有辦法走到頂點 $1$ 或頂點 $2$，因此下面的圖不是一個強連通圖：

對于下圖來說，$1\to 2\to 3\to 4$ 是一條從頂點 $1$ 到頂點 $4$的路徑。$2\to 3\to 4\to 2\to 3$ 就不是一個路徑，因為相同的邊 $(2,3)$ 被多次走到了。$1\to 2\to 3\to 1$ 就是一個回路，因為這個路徑的起點和終點相同：

圖的遍歷

圖通常采用 深度優(yōu)先搜索/ 廣度優(yōu)先搜索 這兩個算法來遍歷。其中深度優(yōu)先算法是最常見的遍歷算法。

對于一個用 鄰接矩陣 保存的圖，其深度優(yōu)先搜索遍歷的 C++ 代碼如下：

int vis[105], map[105][105];void dfs(int node){if (vis[node]) return ;vis[node] = 1;cout << node << endl;for (int i=1; i<=n; i++)if (map[node][i] != -0x7f7f7f7f)dfs(i);return ;
}// 函數(shù)調(diào)用：dfs(1); 表示從1號頂點開始遍歷。

對于一個用 鄰接表 保存的圖，其深度優(yōu)先搜索遍歷的 C++ 代碼如下：

#include <vector>
vector<int> G[105];
int vis[105];void dfs(int node){if (vis[node]) return ;vis[node] = 1;cout << node << endl;for (int to : G[node])dfs(to);return ;
}// 函數(shù)調(diào)用：dfs(1); 表示從1號頂點開始遍歷。

廣度優(yōu)先搜索的方式也類似：

#include <queue>
vector<int> G[105];
int vis[105];void bfs(int node){queue<int> que;que.push(node);while(!que.empty()){int t = que.front();cout << t << endl;que.pop();for (int to : G[node]){if (!vis[to]) {vis[to] = 1;que.push(to);}}}return ;
}// 函數(shù)調(diào)用：bfs(1); 表示從1號頂點開始遍歷。

對于判斷無向圖的連通性，我們只需要從任意一個點開始跑一遍深搜或者廣搜就行了。如果所有頂點的 vis 都被標記了，則證明圖是聯(lián)通的，否則圖就是不連通的。

例題講解

P3916 圖的遍歷

模板題目，從每一個頂點開始用深搜遍歷一遍就可以了。但從每一個點考慮能走到的最大點比較麻煩，一個更優(yōu)的解決辦法是反向建邊，從最大的點開始遍歷，這樣子就可以一次性計算出多個結(jié)果。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;const int N = 10005;
int n, m, ans, vis[N];
vector<int> G[N];void dfs(int node, int d){if (vis[node]) return ;vis[node] = d;ans = max(node, ans);for (int to : G[node]) dfs(to, d);return ;
}int main(){cin >> n >> m;for (int i=0, u, v; i<m; i++){cin >> u >> v;G[v].push_back(u);  // 反向建邊。}for (int i=n; i>=1; i--) dfs(i, i);for (int i=1; i<=n; i++) cout << vis[i] << ' ';return 0;
}

P5318 【深基18.例3】查找文獻

也是一道模板題目，正常遍歷即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100005;int n, m;
int vis1[MAXN], vis2[MAXN];
queue<int> que;
vector<int> G[MAXN];void dfs(int node, int current){vis1[node] = 1;cout << node << ' ';if (current == n) return ;for (int i=0; i<G[node].size(); i++){if (vis1[G[node][i]]) continue;dfs(G[node][i], current+1);}return ;
}void dfs(int node){vis2[node] = 1;que.push(node);while(que.size()){int t = que.front();cout << t << " ";for (int i=0; i<G[t].size(); i++){if (vis2[G[t][i]]) continue;vis2[G[t][i]] = 1;que.push(G[t][i]);}que.pop();}return ;
}int main(){cin >> n >> m;for (int i=0; i<m; i++){int t1, t2;cin >> t1 >> t2;G[t1].push_back(t2);}for (int i=1; i<=n; i++) sort(G[i].begin(), G[i].end());dfs(1, 0), cout << endl, dfs(1);return 0;
}

番外 - 圖的常見算法

更多關(guān)于圖論的算法，請持續(xù)關(guān)注后續(xù)更新。

1. 深度優(yōu)先搜索 (DFS)：適用于遍歷圖和檢測圖中的回路。
2. 廣度優(yōu)先搜索 (BFS)：適用于尋找最短路徑（無權(quán)圖）。
3. Dijkstra 算法：適用于加權(quán)圖中尋找單源最短路徑。
4. Bellman-Ford 算法：適用于有負權(quán)邊的圖中尋找單源最短路徑。
5. Floyd-Warshall 算法：適用于尋找所有頂點對之間的最短路徑。
6. Kruskal 算法：用于求解最小生成樹 (MST - Minimum Spanning Tree)。
7. Prim 算法：另一種求解最小生成樹的方法。
8. 拓撲排序 (Topological Sorting)：適用于有向無環(huán)圖 (DAG)，用于任務(wù)調(diào)度等應(yīng)用。
9. Tarjan 算法：用于求解圖中的強連通分量、割點、橋。