圖的概念、性質和存儲與簡單遍歷

前置知識：樹的基本概念及性質

為了保證學習效果，請保證已經掌握前置知識之后，再來學習本章節！如果在閱讀中遇到困難，也可以回到前面章節查閱。

學習目標

掌握圖的基本概念
掌握圖的一些性質

圖的概念

基本概念

圖 (Graph)?是一個二元組?𝐺=(𝑉(𝐺),𝐸(𝐺))G=(V(G),E(G))?。其中?𝑉(𝐺)V(G)?是非空集，稱為?點集 (Vertex set)?，對于?𝑉V?中的每個元素，我們稱其為?頂點 (Vertex)?或?節點 (Node)?，簡稱?點?；?𝐸(𝐺)E(G)?為?𝑉(𝐺)V(G)?各結點之間邊的集合，稱為?邊集 (Edge set)?。

常用?𝐺=(𝑉,𝐸)G=(V,E)?表示圖。

當?𝑉,𝐸V,E?都是有限集合時，稱?𝐺G?為?有限圖?。

當?𝑉V?或?𝐸E?是無限集合時，稱?𝐺G?為?無限圖?。

圖有多種，包括?無向圖 (Undirected graph)?，?有向圖 (Directed graph)?，?混合圖 (Mixed graph)?等

若?𝐺G?為無向圖，則?𝐸E?中的每個元素為一個無序二元組?(𝑢,𝑣)(u,v)?，稱作?無向邊 (Undirected edge)?，簡稱?邊 (Edge)?，其中?𝑢,𝑣∈𝑉u,v∈V?。設?𝑒=(𝑢,𝑣)e=(u,v)?，則?𝑢u?和?𝑣v?稱為?𝑒e?的?端點 (Endpoint)?。

若?𝐺G?為混合圖，則?𝐸E?中既有向邊，又有無向邊。

若?𝐺G?的每條邊?𝑒𝑘=(𝑢𝑘,𝑣𝑘)ek?=(uk?,vk?)?都被賦予一個數作為該邊的?權?，則稱?𝐺G?為?賦權圖?。如果這些權都是正實數，就稱?𝐺G?為?正權圖?。

形象地說，圖是由若干點以及連接點與點的邊構成的。

圖上的關系

點與點——鄰接

在無向圖?𝐺=(𝑉,𝐸)G=(V,E)?中，對于兩頂點?𝑢u?和?𝑣v?，若存在邊?(𝑢,𝑣)(u,v)?，則稱?𝑢u?和?𝑣v?是?相鄰（鄰接）的?。

一個頂點?𝑣∈𝑉v∈V?的?鄰域 (Neighborhood)?是所有與之相鄰的頂點所構成的集合，記作?𝑁(𝑣)N(v)?。

PS：鄰接表存儲的就是鄰域，并且由此得名。

點與邊——關聯

在無向圖?𝐺=(𝑉,𝐸)G=(V,E)?中，若點?𝑣v?是邊?𝑒e?的一個端點，則稱?𝑣v?和?𝑒e?是?關聯的。

度數

與一個頂點?𝑣v?關聯的邊的條數稱作該頂點的?度 (Degree)?，記作?𝑑(𝑣)d(v)?。特別地，對于邊?(𝑣,𝑣)(v,v)?，則每條這樣的邊要對?𝑑(𝑣)d(v)?產生?22?的貢獻。

對于無向簡單圖，有?𝑑(𝑣)=∣𝑁(𝑣)∣d(v)=∣N(v)∣?。

握手定理（又稱圖論基本定理）：對于任何無向圖?𝐺=(𝑉,𝐸)G=(V,E)?，有?∑𝑣∈𝑉𝑑(𝑣)=2∣𝐸∣∑v∈V?d(v)=2∣E∣?，即無向圖中結點度數的總和等于邊數的兩倍。有向圖中結點的入度之和等于出度之和等于邊數。

推論：?在任意圖中，度數為奇數的點必然有偶數個。

證明：反證法

簡單圖

自環 (Loop)?：對?𝐸E?中的邊?𝑒=(𝑢,𝑣)e=(u,v)?，若?𝑢=𝑣u=v?，則?𝑒e?被稱作一個自環。

重邊/平行邊 (Multiple edge)?：若?𝐸E?中存在兩個完全相同的元素（邊）?𝑒1,𝑒2e1?,e2??，則它們被稱作（一組）重邊。

簡單圖 (Simple graph)?：若一個圖中?沒有自環和重邊，它被稱為簡單圖。非空簡單無向圖中一定存在度相同的結點。

如果一張圖中有自環或重邊，則稱它為?多重圖 (Multigraph)?。

? 在無向圖中?(𝑢,𝑣)(u,v)?和?(𝑣,𝑢)(v,u)?算一組重邊，而在有向圖中，?𝑢→𝑣u→v?和?𝑣→𝑢v→u?不為重邊。

? 在題目中，如果沒有特殊說明，是可以存在自環和重邊的，在做題時需特殊考慮。

路徑

途徑 (Walk)?/?鏈 (Chain)?：一個點和邊的交錯序列，其中首尾是點——?𝑣0,𝑒1,𝑣1,𝑒2,𝑣2,…,𝑒𝑘,𝑣𝑘v0?,e1?,v1?,e2?,v2?,…,ek?,vk??，有時簡寫為?𝑣0→𝑣1→𝑣2→?→𝑣𝑘v0?→v1?→v2?→?→vk??。其中?𝑒𝑖ei??的兩個端點分別為?𝑣𝑖?1vi?1??和?𝑣𝑖vi??。通常來說，邊的數量?𝑘k?被稱作這條途徑的?長度?（如果邊是帶權的，長度通常指路徑上的邊權之和，題目中也可能另有定義）。（以下設?𝑤=[𝑣0,𝑒1,𝑣1,𝑒2,𝑣2,?,𝑒𝑘,𝑣𝑘]w=[v0?,e1?,v1?,e2?,v2?,?,ek?,vk?]?。)

跡 (Trail)?：對于一條途徑?𝑤w?，若?𝑒1,𝑒2,?,𝑒𝑘e1?,e2?,?,ek??兩兩互不相同，則稱?𝑤w?是一條跡。

路徑 (Path)?（又稱?簡單路徑 (Simple path)?)：對于一條跡?𝑤w?，除了?𝑣0v0??和?𝑣𝑘vk??允許相同外，其余點兩兩互不相同，則稱?𝑤w?是一條路徑。

回路 (Circuit)?：對于一個跡?𝑤w?，若?𝑣0=𝑣𝑘v0?=vk??，則稱?𝑤w?是一個回路。

環/圈 (Cycle)?（又稱?簡單回路/簡單環 (Simple circuit)?)：對于一條簡單路徑?𝑤w?，若?𝑣0=𝑣𝑘v0?=vk??，則稱?𝑤w?是一個環。

!!! warning
關于路徑的定義在不同地方可能有所不同，如，“路徑”可能指本文中的“途徑”，“環”可能指本文中的“回路”。如果在題目中看到類似的詞匯，且沒有“簡單路徑”/“非簡單路徑”（即本文中的“途徑”）等特殊說明，最好詢問一下具體指什么。

連通

無向圖

對于一張無向圖?𝐺=(𝑉,𝐸)G=(V,E)?，對于?𝑢,𝑣∈𝑉u,v∈V?，若存在一條途徑使得?𝑣0=𝑢,𝑣𝑘=𝑣v0?=u,vk?=v?，則稱?𝑢u?和?𝑣v?是?連通的 (Connected)?。由定義，任意一個頂點和自身連通，任意一條邊的兩個端點連通。

若無向圖?𝐺=(𝑉,𝐸)G=(V,E)?，滿足其中任意兩個頂點均連通，則稱?𝐺G?是?連通圖 (Connected graph)?，?𝐺G?的這一性質稱作?連通性 (Connectivity)?。

若?𝐻H?是?𝐺G?的一個連通子圖，且不存在?𝐹F?滿足?𝐻?𝐹?𝐺H?F?G?且?𝐹F?為連通圖，則?𝐻H?是?𝐺G?的一個?連通塊/連通分量 (Connected component)?（極大連通子圖）。

有向圖

對于一張有向圖?𝐺=(𝑉,𝐸)G=(V,E)?，對于?𝑢,𝑣∈𝑉u,v∈V?，若存在一條途徑使得?𝑣0=𝑢,𝑣𝑘=𝑣v0?=u,vk?=v?，則稱?𝑢u?可達?𝑣v?。由定義，任意一個頂點可達自身，任意一條邊的起點可達終點。（無向圖中的連通也可以視作雙向可達。）

若一張有向圖的節點兩兩互相可達，則稱這張圖是?強連通的 (Strongly connected)?。

若一張有向圖的邊替換為無向邊后可以得到一張連通圖，則稱原來這張有向圖是?弱連通的 (Weakly connected)?。

與連通分量類似，也有?弱連通分量 (Weakly connected component)?（極大弱連通子圖）和?強連通分量 (Strongly Connected component)?（極大強連通子圖）。

𝑛n?個頂點的強連通圖最多?𝑛(𝑛?1)n(n?1)?條邊，最少?𝑛n?條邊。

圖的連通性也是競賽的一個常見考點，相關算法請后面將學習，現在先理解其概念即可。

稀疏圖/稠密圖

若一張圖的邊數遠小于其點數的平方，那么它是一張?稀疏圖 (Sparse graph)?。

若一張圖的邊數接近其點數的平方，那么它是一張?稠密圖 (Dense graph)?。

這兩個概念并沒有嚴格的定義，一般用于討論?時間復雜度?為?𝑂(∣𝑉∣2)O(∣V∣2)?的算法與?𝑂(∣𝐸∣)O(∣E∣)?的算法的效率差異（在稠密圖上這兩種算法效率相當，而在稀疏圖上?𝑂(∣𝐸∣)O(∣E∣)?的算法效率明顯更高）。

特殊的圖

完全圖

若無向簡單圖?𝐺G?滿足任意不同兩點間均有邊，則稱?𝐺G?為?完全圖 (Complete graph)?，?𝑛n?階完全圖記作?𝐾𝑛Kn??。若有向圖?𝐺G?滿足任意不同兩點間都有兩條方向不同的邊，則稱?𝐺G?為?有向完全圖 (Complete digraph)?。

環圖/圈圖

若無向簡單圖?𝐺=(𝑉,𝐸)G=(V,E)?的所有邊恰好構成一個圈，則稱?𝐺G?為?環圖/圈圖 (Cycle graph)?，?𝑛n?(?𝑛≥3n≥3?) 階圈圖記作?𝐶𝑛Cn??。易知，一張圖為圈圖的充分必要條件是，它是?22?- 正則連通圖。

星圖/菊花圖

若無向簡單圖?𝐺=(𝑉,𝐸)G=(V,E)?滿足，存在一個點?𝑣v?為支配點，其余點之間沒有邊相連，則稱?𝐺G?為?星圖/菊花圖 (Star graph)?，?𝑛+1n+1?(?𝑛≥1n≥1?) 階星圖記作?𝑆𝑛Sn??。

輪圖

若無向簡單圖?𝐺=(𝑉,𝐸)G=(V,E)?滿足，存在一個點?𝑣v?為支配點，其它點之間構成一個圈，則稱?𝐺G?為?輪圖 (Wheel Graph)?，?𝑛+1n+1?(?𝑛≥3n≥3?) 階輪圖記作?𝑊𝑛Wn??。

鏈

若無向簡單圖?𝐺=(𝑉,𝐸)G=(V,E)?的所有邊恰好構成一條簡單路徑，則稱?𝐺G?為?鏈 (Chain/Path Graph)?，?𝑛n?階的鏈記作?𝑃𝑛Pn??。易知，一條鏈由一個圈圖刪去一條邊而得。

樹

如果一張無向連通圖不含環，則稱它是一棵?樹 (Tree)?。相關內容詳見樹基礎。

補圖

對于無向簡單圖?𝐺=(𝑉,𝐸)G=(V,E)?，它的?補圖 (Complement graph)?指的是這樣的一張圖：記作?𝐺ˉGˉ?，滿足?𝑉(𝐺ˉ)=𝑉(𝐺)V(Gˉ)=V(G)?，且對任意節點對?(𝑢,𝑣)(u,v)?，?(𝑢,𝑣)∈𝐸(𝐺ˉ)(u,v)∈E(Gˉ)?當且僅當?(𝑢,𝑣)?𝐸(𝐺)(u,v)∈/E(G)?。

反圖

對于有向圖?𝐺=(𝑉,𝐸)G=(V,E)?，它的?反圖 (Transpose Graph)?指的是點集不變，每條邊反向得到的圖，即：若?𝐺G?的反圖為?𝐺′=(𝑉,𝐸′)G′=(V,E′)?，則?𝐸′={(𝑣,𝑢)∣(𝑢,𝑣)∈𝐸}E′={(v,u)∣(u,v)∈E}?。

平面圖

如果一張圖可以畫在一個平面上，且沒有兩條邊在非端點處相交，那么這張圖是一張?平面圖 (Planar graph)?。一張圖的任何子圖都不是?𝐾5K5??或?𝐾3,3K3,3??是其為一張平面圖的充要條件。對于簡單連通平面圖?𝐺=(𝑉,𝐸)G=(V,E)?且?𝑉≥3V≥3?，?∣𝐸∣≤3∣𝑉∣?6∣E∣≤3∣V∣?6?。

學習目標

掌握圖的四種存儲方法的代碼實現
理解圖的四種存儲方法各自的時間空間復雜度
能夠根據題目的要求和數據范圍，選擇合適存圖方式

圖的邏輯結構

一張圖是由節點和邊構成的，一個無向圖如下圖所示：

什么叫?「邏輯結構」？就是說為了方便研究，我們把圖?抽象?成這個樣子。

根據這個邏輯結構，我們可以認為每個節點的實現如下：

// 圖節點的邏輯結構
struct node {int data;                 // 存當前結點信息vector<int> neighbors;  // 存鄰接的所有結點
}

看到這個實現，你有沒有很熟悉？它和我們之前說的多叉樹節點幾乎完全一樣：

// 樹節點的邏輯結構
struct node {int data;                 // 存當前結點信息vector<int> son;        // 存所有的子結點
}

Copy

不過呢，上面的這種實現是「邏輯上的」，實際上我們很少用這個node類實現圖，而是用接下來介紹的幾種方法去存儲。其中包含我們前面經常提到的?鄰接表和鄰接矩陣。

圖的存儲方法

接下來描述圖的具體四種存儲方式，這四種方式是我們今后和圖這種數據結構打交道的接口，請一定要掌握。

首先約定，用?𝑛n?代指圖的點數，用?𝑚m?代指圖的邊數，用?𝑑+(𝑢)d+(u)?代指點?𝑢u?的出度，即以?𝑢u?為出發點的邊數。

直接存邊

方法

使用一個數組來存邊，數組中的每個元素都包含一條邊的起點與終點（帶邊權的圖還包含邊權）。（或者使用多個數組分別存起點，終點和邊權。）

#include <iostream>
#include <vector>
using namespace std;struct Edge {int u, v, w;   // 一條邊的 起點、終點、權值
};int n, m;
vector<Edge> e;
vector<bool> vis;// 函數功能：判斷 u,v 之間有沒有邊
bool find_edge(int u, int v) {for (int i = 1; i <= m; ++i) {if (e[i].u == u && e[i].v == v) {return true;}}return false;
}// 遍歷圖
void dfs(int u) {if (vis[u]) return;vis[u] = true;for (int i = 1; i <= m; ++i) {if (e[i].u == u) {dfs(e[i].v);}}
}int main() {cin >> n >> m;// 初始化 vector 數組，也可以將 vis 定義成: “bool vis[N];” 以省去初始化。下同vis.resize(n + 1, false);e.resize(m + 1);for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v >> e[i].w;return 0;
}

復雜度

查詢是否存在某條邊：?𝑂(𝑚)O(m)?。

遍歷一個點的所有出邊：?𝑂(𝑚)O(m)?。

遍歷整張圖：?𝑂(𝑛𝑚)O(nm)?。

空間復雜度：?𝑂(𝑚)O(m)?。

應用

由于直接存邊的遍歷效率低下，一般不用于遍歷圖。

在 Kruskal 算法中，由于需要將邊按邊權排序，需要直接存邊。

在有的題目中，需要多次建圖（如建一遍原圖，建一遍反圖），此時既可以使用多個其它數據結構來同時存儲多張圖，也可以將邊直接存下來，需要重新建圖時利用直接存下的邊來建圖。

鄰接矩陣

方法

使用一個二維數組?g?來存邊，其中?g[u][v]?為 1 表示存在?𝑢u?到?𝑣v?的邊，為 0 表示不存在。

如果是帶邊權的圖，可以在?g[u][v]?中存儲?𝑢u?到?𝑣v?的邊的邊權，0 表示沒有連接，其他值表示權重。

如果是無向圖，則將一條無向邊拆成兩條方向相反的邊即可。（所謂的「無向」，也就等同于「雙向」）

#include <iostream>
#include <vector>
using namespace std;const int N = 1e5+5;
int n, m;
bool vis[N];
bool g[N][N];bool find_edge(int u, int v) { return g[u][v]; }void dfs(int u) {if (vis[u]) return;vis[u] = true;for (int v = 1; v <= n; ++v) {if (g[u][v]) {dfs(v);}}
}int main() {cin >> n >> m;fill_n(vis, N, false);  // 將 vis 數組清 false，類似 memsetfill_n(g, N*N, false);for (int i = 1; i <= m; ++i) {int u, v;cin >> u >> v;g[u][v] = true;   // u->v 有條單向邊// 如果是雙向邊// g[u][v] = g[v][u] = true;}return 0;
}

復雜度

查詢是否存在某條邊：?𝑂(1)O(1)?。

遍歷一個點的所有出邊：?𝑂(𝑛)O(n)?。

遍歷整張圖：?𝑂(𝑛2)O(n2)?。

空間復雜度：?𝑂(𝑛2)O(n2)?。

應用

鄰接矩陣只適用于沒有重邊（或重邊可以忽略）的情況。

其最顯著的優點是可以?𝑂(1)O(1)?查詢一條邊是否存在。

由于鄰接矩陣在稀疏圖上效率很低（尤其是在點數較多的圖上，空間無法承受），所以一般只會?在稠密圖上使用鄰接矩陣。并且，在稠密圖上使用鄰接矩陣的運行效率遠高于鄰接表，這是因為 CPU 中順序訪問的速度是遠高于隨機訪問的（緩存命中）。

鄰接表

方法

使用一個支持動態增加元素的數據結構構成的數組，如?vector<int> g[N]?來存邊，其中?g[u]?存儲的是點?𝑢u?的所有出邊的相關信息（終點、邊權等）。

#include <iostream>
#include <vector>
using namespace std;const int N = 1e5+5;
int n, m;
bool vis[N];
vector<int> g[N];bool find_edge(int u, int v) {for (int i = 0; i < g[u].size(); ++i) {if (g[u][i] == v) {return true;}}return false;
}void dfs(int u) {if (vis[u]) return;vis[u] = true;for (int i = 0; i < g[u].size(); ++i) dfs(g[u][i]);
}int main() {cin >> n >> m;vis.resize(n + 1, false);g.resize(n + 1);for (int i = 1; i <= m; ++i) {int u, v;cin >> u >> v;g[u].push_back(v);// 如果是無向圖，還須：// g[v].push_back(u);}return 0;
}

復雜度

查詢是否存在?𝑢u?到?𝑣v?的邊：?𝑂(𝑑+(𝑢))O(d+(u))?（如果事先進行了排序就可以使用二分查找做到?𝑂(log?(𝑑+(𝑢)))O(log(d+(u)))?）。

遍歷點?𝑢u?的所有出邊：?𝑂(𝑑+(𝑢))O(d+(u))?。

遍歷整張圖：?𝑂(𝑛+𝑚)O(n+m)?。

空間復雜度：?𝑂(𝑚)O(m)?。

應用

存各種圖都很適合，除非有特殊需求（如需要快速查詢一條邊是否存在，且點數較少，可以使用鄰接矩陣）。

尤其適用于需要對一個點的所有出邊進行排序的場合。

鏈式前向星

方法

本質上是用鏈表實現的鄰接表，示例代碼如下：

#include <iostream>
#include <vector>
using namespace std;const int N = 1e5+5;
int n, m;bool vis[N];
int head[N], nxt[N], to[N], cnt;     // 鏈式前向星三要素void add(int u, int v) {     // 添加一條 u->v 的邊nxt[++cnt] = head[u];    // cnt 這條邊的后繼（同是 u 的出邊的上一條邊）to[cnt] = v;             // 當前邊的終點是 vhead[u] = cnt;           // 起點 u 的第一條邊放到了下標 cnt 處（其實是最后一條）
}bool find_edge(int u, int v) {for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1if (to[i] == v) {return true;}}return false;
}void dfs(int u) {if (vis[u]) return;vis[u] = true;cout << u << ' ';for (int i = head[u]; ~i; i = nxt[i])dfs(to[i]);
}int main() {cin >> n >> m;fill_n(vis, N, false);fill_n(head, N, -1);for (int i = 1; i <= m; ++i) {int u, v;cin >> u >> v;add(u, v);}dfs(1);return 0;
}

如果圖是賦權圖，即邊帶有權重時，此時數組定義過多，也可以寫成結構體去保存，參考代碼如下：

#include<bits/stdc++.h>
using namespace std;const int N = 1e5;    //點數最大值
int n, m;             //n個點，m條邊
int head[N], cnt = -1;     //head[i],表示以i為起點的第一條邊在邊集數組的位置（編號）struct Edge
{int to, w, next;   // 終點，邊權，同起點的上一條邊的編號
}edge[N];//邊集void add_edge(int u, int v, int w)// 加邊，u 起點，v 終點，w 邊權
{edge[++cnt].next = head[u];    // 以u為起點上一條邊的編號，也就是與這個邊起點相同的上一條邊的編號edge[cnt].to = v;          // 終點edge[cnt].w = w;             // 權值head[u] = cnt;               // 更新以u為起點上一條邊的編號
}
int main()
{cin >> n >> m;int u, v, w;fill_n(head, N, -1);for (int i = 1; i <= m; i++) // 輸入m條邊{cin >> u >> v >> w;add_edge(u, v, w);       // 加邊// 加雙向邊// add_edge(u, v, w);// add_edge(v, u, w);}// 輸出每個結點的出邊for (int i = 1; i <= n; i++){cout << i << endl;for (int j = head[i]; ~j; j = edge[j].next)  // 遍歷以 i為起點的邊{cout << i << " " << edge[j].to << " " << edge[j].w << endl;}cout << endl;}return 0;
}
/*
5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7
*/

復雜度

查詢是否存在?𝑢u?到?𝑣v?的邊：?𝑂(𝑑+(𝑢))O(d+(u))?。

遍歷點?𝑢u?的所有出邊：?𝑂(𝑑+(𝑢))O(d+(u))?。

遍歷整張圖：?𝑂(𝑛+𝑚)O(n+m)?。

空間復雜度：?𝑂(𝑚)O(m)?。

應用

注意：利用鏈式前向星遍歷的邊的順序和輸入順序是相反的！

存各種圖都很適合，但是缺點也很明顯，?不能快速查詢一條邊是否存在，也不能方便地對一個點的出邊進行排序。

優點是邊是帶編號的，有時會非常有用，而且如果邊是從數組的偶數位開始存儲（按上面示例代碼寫法是從 0 開始存儲的，cnt?的初始值為 -1），存雙向邊時?i ^ 1?即是?i?的反邊（常用于網絡流）。

總結

圖的存儲方法比較多，每種方法各有優缺點，對比如下：

	直接存邊	鄰接矩陣	鄰接表	鏈式前向星
使用場合	需要將邊按邊權排序時；需要重新建圖時利用直接存下的邊來建圖	只適用于沒有重邊（或重邊可以忽略）的情況；可以?𝑂(1)O(1)?查詢邊；在稠密圖上效率很高	消耗空間較小，各種場合都適用，尤其適用于需要對點的出邊排序的場合	消耗空間小，各種場合都適用
缺點	遍歷效率低下，一般不用于遍歷圖	只適用于沒有重邊（或重邊可以忽略）的情況。	需熟練掌握 vector 操作？	不能迅速查詢邊和對一個點的出邊排序