圖論是NOIP的一個(gè)非常重要的考點(diǎn)，換句話說，沒有圖論，NOIP的考綱就得少一大半（雖然很NOIP沒有考綱）

圖論這玩意吧，和數(shù)論一樣是非常變態(tài)的東西，知識(shí)點(diǎn)又多又雜，但是好在一個(gè)事，他比較直觀比較好想

圖

對(duì)于一張圖而言，我們定義圖是一種由邊和點(diǎn)構(gòu)成的的一個(gè)玩意（其實(shí)是嚴(yán)謹(jǐn)定義我記不住了QWQ，但是不影響學(xué)習(xí)）

一般來說，圖的存儲(chǔ)難度主要在記錄邊的信息
無向圖的存儲(chǔ)中，只需要將一條無向邊拆成兩條即可
鄰接矩陣：用一個(gè)二維數(shù)組 edg[N][N] 表示
edg[i][j] 就對(duì)應(yīng)由 i 到 j 的邊信息
edg[i][j] 可以記錄 Bool，也可以記錄邊權(quán)
缺點(diǎn)：如果有重邊有時(shí)候不好處理
空間復(fù)雜度 O(V^2)

點(diǎn)度等額外信息也是很好維護(hù)的

#include <bits/stdc++.h>using namespace std;const int N = 5005;int ideg[N], odeg[N], n, m, edg[N][N]; bool visited[N];void travel(int u, int distance) {cout << u << " " << distance << endl; visited[u] = true;for (int v = 1; v <= n; v++)if (edg[u][v] != -1 && !visited[v])//是否已經(jīng)訪問過 travel(v, distance + edg[u][v]); //if there is an edge (u, v) and v has not been visited, then travel(v) } int main() {cin >> n >> m;memset(edg, -1, sizeof edg);memset(visited, false, sizeof visited);for (int u, v, w, i = 1; i <= m; i++)cin >> u >> v >> w, edg[u][v] = w, odeg[u]++, ideg[v]++;//出度和入度 for (int i = 1; i <= n; i++)cout << ideg[i] << " " << odeg[i] << endl;for (int i = 1; i <= n; i++)if (!visited[i]) travel(i, 0); }/* Given a graph with N nodes and M unidirectional edges. Each edge e_i starts from u_i to v_i and weights w_i Output a travelsal from node 1 and output degree of each node. */

其實(shí)這個(gè)英文注釋也還蠻不錯(cuò)的啊

鄰接矩陣本質(zhì)上其實(shí)就是一個(gè)二維數(shù)組，它在存儲(chǔ)一個(gè)稠密圖的時(shí)候效率比較好，但是稀松圖的話就非常浪費(fèi)空間

所以我們就沒有必要用二維數(shù)組記錄信息，我們只需要對(duì)每一個(gè)點(diǎn)記錄他的出邊就行

這樣記的話，復(fù)雜度就是他的邊數(shù)

對(duì)每一個(gè)點(diǎn) u 記錄一個(gè) List[u]，包含所有從 u 出發(fā)的邊
直接用數(shù)組實(shí)現(xiàn) List[u]？讀入邊之前不知道 List[u] 長(zhǎng)度
手寫鏈表（鏈?zhǔn)角跋蛐?#xff09;
用 STL 中的 vector 實(shí)現(xiàn)變長(zhǎng)數(shù)組，當(dāng)然你想要手寫指針也沒問題
只需要 O(V + E) 的空間就能實(shí)現(xiàn)圖的存儲(chǔ)（邊數(shù)加點(diǎn)數(shù)）

其實(shí)寫這個(gè)鏈表存儲(chǔ)0有很多方式啊，你可以用指針，手寫指針，也可以用vector ，還可以用數(shù)組毛模擬

我們?cè)敿?xì)理解一下代碼

#include <bits/stdc++.h>using namespace std;const int N = 5005;struct edge {int u, v, w; edge *next;//next指針指向 edge(int _u, int _v, int _w, edge *_next):u(_u), v(_v), w(_w), next(_next) {} }; edge *head[N]; //List[u] 最前面的節(jié)點(diǎn)是誰 int ideg[N], odeg[N], n, m; bool visited[N];void add(int u, int v, int w) {edge *e = new edge(u, v, w, head[u]);head[u] = e; } void travel(int u, int distance) {cout << u << " " << distance << endl; visited[u] = true;for (edge *e = head[u]; e ; e = e -> next)if (!visited[e -> v])travel(e -> v, distance + e -> w); //if there is an edge (u, v) and v has not been visited, then travel(v) } int main() {cin >> n >> m;memset(visited, false, sizeof visited);memset(head, 0, sizeof head);for (int u, v, w, i = 1; i <= m; i++)cin >> u >> v >> w, add(u, v, w), odeg[u]++, ideg[v]++;for (int i = 1; i <= n; i++)cout << ideg[i] << " " << odeg[i] << endl;for (int i = 1; i <= n; i++)if (!visited[i]) travel(i, 0); }/* Given a graph with N nodes and M unidirectional edges. Each edge e_i starts from u_i to v_i and weights w_i Output a travelsal from node 1 and output degree of each node. */

但是我個(gè)人是不用指針的，因?yàn)榭赡苓€是不習(xí)慣的原因吧，而且指針的寫法并沒有什么特別的優(yōu)點(diǎn)

還有一個(gè)數(shù)組模擬版本

#include <bits/stdc++.h>using namespace std;const int N = 5005;struct edge {int u, v, w, next; }edg[N]; int head[N]; //List[u] stores all edges start from u int ideg[N], odeg[N], n, m, cnt; //cnt: numbers of edges bool visited[N];void add(int u, int v, int w) {int e = ++cnt;edg[e] = (edge){u, v, w, head[u]};head[u] = e; } void travel(int u, int distance) {cout << u << " " << distance << endl; visited[u] = true;for (int e = head[u]; e ; e = edg[e].next)if (!visited[edg[e].v])travel(edg[e].v, distance + edg[e].w); //if there is an edge (u, v) and v has not been visited, then travel(v) } int main() {cin >> n >> m; cnt = 0;memset(visited, false, sizeof visited);memset(head, 0, sizeof head);for (int u, v, w, i = 1; i <= m; i++)cin >> u >> v >> w, add(u, v, w), odeg[u]++, ideg[v]++;for (int i = 1; i <= n; i++)cout << ideg[i] << " " << odeg[i] << endl;for (int i = 1; i <= n; i++)if (!visited[i]) travel(i, 0); }/* Given a graph with N nodes and M unidirectional edges. Each edge e_i starts from u_i to v_i and weights w_i Output a travelsal from node 1 and output degree of each node. */

但是數(shù)組模擬必然是逃不開浪費(fèi)時(shí)間過多的，這個(gè)事就很討厭了，鄰接矩陣以其優(yōu)秀的可讀性以及構(gòu)造性換來了不少空間，唉

我個(gè)人現(xiàn)在是這樣的，判斷變數(shù)和點(diǎn)數(shù)的值，如果差別較大，那么出題人可能是想構(gòu)造菊花樹之類的，差別較小就意味著稠密，那么寫鄰接矩陣更節(jié)省時(shí)間（前提是你兩個(gè)都能用）

還有一種寫法是用vector

拋去鄰接矩陣不講，如果我們用edg[u][i]表示從u出發(fā)的第i條邊，這樣實(shí)際上還是O(n^2)的，所以我們要用一個(gè)能夠自己改變長(zhǎng)度的STL，這樣能讓空間最大化

#include <bits/stdc++.h>using namespace std;const int N = 5005;struct edge {int u, v, w; }; vector<edge> edg[N]; //edge記錄變長(zhǎng)數(shù)組記錄的是什么類型 int ideg[N], odeg[N], n, m, cnt; //cnt: numbers of edges bool visited[N];void add(int u, int v, int w) {edg[u].push_back((edge){u, v, w});//一個(gè)強(qiáng)制類型轉(zhuǎn)換 } void travel(int u, int distance) {cout << u << " " << distance << endl; visited[u] = true;for (int e = 0; e < edg[u].size(); e++)//遍歷邊 if (!visited[edg[u][e].v])//以u(píng)出發(fā)的第e條出邊 travel(edg[u][e].v, distance + edg[u][e].w); //if there is an edge (u, v) and v has not been visited, then travel(v) } int main() {cin >> n >> m; cnt = 0;memset(visited, false, sizeof visited);for (int u, v, w, i = 1; i <= m; i++)cin >> u >> v >> w, add(u, v, w), odeg[u]++, ideg[v]++;for (int i = 1; i <= n; i++)cout << ideg[i] << " " << odeg[i] << endl;for (int i = 1; i <= n; i++)if (!visited[i]) travel(i, 0); }/* Given a graph with N nodes and M unidirectional edges. Each edge e_i starts from u_i to v_i and weights w_i Output a travelsal from node 1 and output degree of each node. */

要注意的是，c++的STL數(shù)組默認(rèn)都是以0為結(jié)尾的、

vector是這樣構(gòu)造的

<>里面寫的是變量類型，可以是int 或者float或者結(jié)構(gòu)體

生成樹

我們考慮一個(gè)聯(lián)通的無向圖，我們考慮找出這個(gè)圖當(dāng)中的子圖（點(diǎn)的數(shù)量是一樣的，可以刪掉邊）

給定一個(gè)連通無向圖 G = (V; E)
E′ ? E
G′ = (V; E′) 構(gòu)成一棵樹
G′ 就是 G 的一個(gè)生成樹

而且我們可以發(fā)現(xiàn)生成樹不是唯一的，而且我們可以知道的是生成樹的數(shù)量是指數(shù)級(jí)別的

那么最小生成樹其實(shí)就是生成樹當(dāng)中最大邊權(quán)的值最小

?怎么求呢？

Algorithms for Minimal Spanning Tree：
Kruskal
Prim
Kosaraju

Kruskal

克魯斯卡爾的思想是貪心加上并查集

我們只把所有的邊的信息存下來，而不用存圖（因?yàn)樽钚∩蓸渲粏柲阕钚∵厵?quán)和之類的問題，而不文）

，對(duì)于所有的邊權(quán)進(jìn)行排序，找到當(dāng)前邊權(quán)最小的邊 e : (u; v)
如果 u 和 v 已經(jīng)連通，則直接刪除這條邊（這里的判斷就是用并查集的思想，如果最終并查集的指向指到了一個(gè)同一個(gè)點(diǎn)，那么就是聯(lián)通的啊）
如果 u 和 v 已經(jīng)未連通，將之加入生成樹
重復(fù)上述過程

這個(gè)稱為Rigorous proof（消圈算法）

Kruskal的證明方法很迷啊，就感性理解一下就好

畢竟貪心這東西證明正確性還是挺困難的。

Prim的做法是，我們找一個(gè)連通塊，我們把和這個(gè)連通塊最短的點(diǎn)加到連通塊當(dāng)中去（這倆都可以用堆優(yōu)化）

Kosaraju的做法是，我們有很多連通塊，然后第一輪的時(shí)候?qū)τ诿恳粋€(gè)連通塊找到和它相連的最短的邊，就把這兩個(gè)集合連接起來

?

轉(zhuǎn)載于:https://www.cnblogs.com/this-is-M/p/10806609.html

總結(jié)

以上是生活随笔為你收集整理的QBXT Day 5图论相关的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。