圖論入門與最短路徑算法

圖的基本概念

由節(jié)點(diǎn)和邊組成的集合

圖的一些概念：

①有向邊（有向圖），無向邊（無向圖），權(quán)值

②節(jié)點(diǎn)（度），對(duì)應(yīng)無向圖，度就是節(jié)點(diǎn)連著幾條邊，對(duì)于有向圖就是出度加入度

③完全連通圖

④子圖

⑤路徑

⑥完全圖，每兩節(jié)點(diǎn)間都有一條邊相連

圖的遍歷：

①：深度優(yōu)先搜索

注意：有向圖和無向圖的遍歷不一樣

②：廣度優(yōu)先搜索

圖的存儲(chǔ)：

鄰接矩陣

①鄰接矩陣->多維數(shù)組（二維，n * n，n為節(jié)點(diǎn)數(shù)）；

設(shè)兩點(diǎn)連通為1

如果有權(quán)值

優(yōu)點(diǎn)：快速且直觀地每兩個(gè)點(diǎn)間的關(guān)系（如果要判斷x和y之間的關(guān)系，直接通過訪問arr[x] [y]或arr[y] [x]獲得兩點(diǎn)信息）

缺點(diǎn)：存儲(chǔ)了一些無用信息，浪費(fèi)空間；不能快速地訪問以某點(diǎn)為起點(diǎn)的所有的邊。

代碼演示：

#include<iostream>
using namespace std;int n, m, arr[105][105];int main() {cin >> n >> m;//n為節(jié)點(diǎn)個(gè)數(shù)//m為邊的個(gè)數(shù)，每條邊帶一個(gè)權(quán)值，一個(gè)循環(huán)把權(quán)值存到數(shù)組里面for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;arr[a][b] = c;}//輸出for (int i = 1; i<= n; i++) {cout << i << ":";for (int j = 1; j <= n; j++) {if (arr[i][j] != 0) {cout << "{" << i << "->" << arr[i][j] << "}";}}cout << endl;}return 0;
}

Floyd算法

算法解決問題：多源（多個(gè)原點(diǎn)）最短路徑問題

核心思想：為了取最小值，所以把所有路徑初始化為最大，一般為0x3F，然后將各種路徑算一遍，取兩點(diǎn)最小距離的路徑作為此最短路徑，因?yàn)閮蓚€(gè)兩點(diǎn)路徑的其中一個(gè)路徑可以從另外兩個(gè)兩點(diǎn)路徑獲得，所以每兩點(diǎn)路徑都是可以用兩點(diǎn)路徑獲得或者兩個(gè)兩點(diǎn)路徑獲得

核心思想圖示：以1->3 ， 1->2->5->4->3為例

核心代碼：

memset(arr, 0x3F, sizeof(arr));//初始化（極大值）
for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {for (itn k = 1; k <= n; k++) {arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);//從j到k的最短路，arr[j][i] + arr[i][k]為經(jīng)過i點(diǎn)中轉(zhuǎn)，從j到i再到k。注意，無論之間有多少個(gè)中轉(zhuǎn)點(diǎn)，每三個(gè)都會(huì)被合并為一個(gè)，比如15234，合并523后會(huì)變成154}}
}

oj746題:

#include<iostream>
#include<cstring>
using namespace std;
int n, m, s, arr[1005][1005];
int main() {memset(arr, 0x3F, sizeof(arr));//初始化（極大值）cin >> n >> m;for (int i = 0; i < m; i++) {//全邊（保留權(quán)值最小的邊）int a, b, c;cin >> a >> b >> c;if (arr[a][b] > c) {arr[a][b] = c;arr[b][a] = c;}}for (int i = 1; i <= n; i++) {//floydfor (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);//從j到k的最短路，arr[j][i] + arr[i][k]為經(jīng)過i點(diǎn)中轉(zhuǎn)，從j到i再到k}}}arr[s][s] = 0;for (int i = 1; i <= n; i++) {if (arr[s][i] = 0x3F3F3F3F) {cout << -1 << endl;//還是原本最大值就說明到不了} else {cout << arr[s][i] << endl;}}return 0;}

鄰接表

鄰接表：構(gòu)建一個(gè)列數(shù)可變的二維數(shù)組，根據(jù)節(jié)點(diǎn)數(shù)定義定義行數(shù)

鄰接表的優(yōu)缺點(diǎn)和鄰接矩陣的優(yōu)缺點(diǎn)互補(bǔ)

優(yōu)點(diǎn)：①、省空間②、快速訪問以某點(diǎn)為起點(diǎn)的所有點(diǎn)

缺點(diǎn)：①不能快速判斷兩點(diǎn)間的關(guān)系

代碼演示：

基礎(chǔ)理解代碼：

#include<iostream>
using namespace std;int n, m, num[105][105][2];int main() {cin >> n >> m;for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;//a為起點(diǎn)節(jié)點(diǎn)，b為終點(diǎn)節(jié)點(diǎn)，c為權(quán)值num[a][++num[a][0][0]][0] = b;num[a][num[a][0][0]][1] = c;}for (int i = 1; i <= n; i++) {cout << i << ":";for (int j = 1; j <= num[i][0][0]; j++) {cout << "{" << num[i][j][0] << "," << num[i][j][1] << "}";}cout << endl;}return 0;
}

全部代碼：

#include<iostream>
#include<vector>
using namespace std;
//保存終點(diǎn)節(jié)點(diǎn)和此路徑的權(quán)值，也可用鍵值對(duì)來保存
struct edge {int e, v;
};int main() {int n, m;cin >> n >> m;//n為節(jié)點(diǎn)數(shù)，m為邊數(shù)vector<vector<edge> > edg(n + 1, vector<edge>());for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;edg[a].push_back((edge){b, c});//a為起點(diǎn)節(jié)點(diǎn)，b為終點(diǎn)節(jié)點(diǎn)，c為權(quán)值}for (int i = 1; i <= n; i++) {cout << i << ":" ;for (int j = 0; j <= edg[i].size(); j++) {cout << "{" << i << "->" << edg[i][j].e << "," << edg[i][j].v << "}";}cout << endl;}return 0;
}

Dijkstra算法

算法解決問題：解決單源（一個(gè)原點(diǎn)）最短路徑的問題

算法前提：不能有負(fù)權(quán)邊，負(fù)環(huán)（在環(huán)的路徑中路徑值無限減小）沒有最短路

核心思想：

用一個(gè)數(shù)組保存一個(gè)能到此節(jié)點(diǎn)的所有的距離

核心思想圖示：

代碼演示：

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;//每個(gè)點(diǎn)的各種狀態(tài)，為了優(yōu)先隊(duì)列為一個(gè)小頂堆，且這個(gè)排序根據(jù)原點(diǎn)到當(dāng)前節(jié)點(diǎn)的距離，排序的目的是為了編號(hào)從小到大去遍歷
struct node {int now, dis;//now為當(dāng)前點(diǎn)，dis為到這的總長度bool operator< (const node &b) const {return this->dis > b.dis;}
};struct edge {int e, v;//e為當(dāng)前點(diǎn)的編號(hào)，v為權(quán)值
};//ans[i]數(shù)組保存是從原點(diǎn)到編號(hào)為i點(diǎn)距離
int n, m, s, ans[100005];int main() {memset(ans, 0x3F, sizeof (ans));cin >> n >> m >> s;//n為節(jié)點(diǎn)數(shù)，m為邊數(shù)，s為源點(diǎn)編號(hào)vector<vector<edge> > edg(n + 1, vector<edge>());for (int i = 0; i < m; i++) {int a, b, c;//a為起點(diǎn)節(jié)點(diǎn)，b為終點(diǎn)節(jié)點(diǎn)，c為權(quán)值cin >> a >> b >> c;//無向圖edg[a].push_back((edge){b, c});edg[b].push_back((edge){a, c});}priority_queue<node> que;//que.push((node){s, 0});//起始元素加入隊(duì)列, now為s，dis為0ans[s] = 0;//起點(diǎn)答案置為0while (!que.empty()) {node temp = que.top();que.pop();if (temp.dis > ans[temp.now]) {//如果答案已被固定，也就是此時(shí)遍歷點(diǎn)的 原點(diǎn)到此點(diǎn)的距離 如果大于 當(dāng)前點(diǎn)的 原點(diǎn)到此點(diǎn)的距離continue;}//遍歷以遍歷點(diǎn)為起點(diǎn)的每一條邊for (int i = 0; i < edg[temp.now].size(); i++) {int e = edg[temp.now][i].e;//temp.now為當(dāng)前的點(diǎn)的編號(hào)，e為當(dāng)前點(diǎn)到達(dá)的終點(diǎn)int v = edg[temp.now][i].v;//v為當(dāng)前點(diǎn)到達(dá)終點(diǎn)的權(quán)值if (ans[e] > ans[temp.now] + v) {//ans[temp.now]保存的是從原點(diǎn)到當(dāng)前點(diǎn)的距離，如果，從原點(diǎn)到當(dāng)前點(diǎn)的距離和當(dāng)前點(diǎn)到某終點(diǎn)的權(quán)值之和小于從原點(diǎn)到當(dāng)前點(diǎn)的距離就把這個(gè)點(diǎn)放到優(yōu)先隊(duì)列，且更新從原點(diǎn)到當(dāng)前點(diǎn)的距離ans[e] = ans[temp.now] + v;que.push((node){e, ans[e]});}}}for (int  i = 1; i <= n; i++) {if (ans[i] == 0x3F3F3F) {cout << -1 << endl;} else {cout << ans[i] <<endl;}}return 0;
}

鏈?zhǔn)角跋蛐?/h5>

靜態(tài)鏈表：用一個(gè)數(shù)組來存節(jié)點(diǎn)，每個(gè)數(shù)組元素包括數(shù)據(jù)域和指針域，指針域保存下一個(gè)節(jié)點(diǎn)的索引

鏈?zhǔn)角跋蛐?#61;>采取頭插法的靜態(tài)鏈表

意義：保存每兩個(gè)有聯(lián)系點(diǎn)

解釋：首先需要兩個(gè)數(shù)組，一個(gè)數(shù)組為head，這個(gè)數(shù)組的索引為各個(gè)起點(diǎn)編號(hào)，head[i]保存的是以i為起點(diǎn)的最后一條邊（最后一個(gè)終點(diǎn)）的編號(hào)；另一個(gè)數(shù)組為靜態(tài)鏈表edg，edg[i].next保存的是以i這條邊同起點(diǎn)的上一條邊的編號(hào)，edg[i].edge保存的是終點(diǎn)編號(hào)。

保存過程：首先根據(jù)一個(gè)起始點(diǎn)的編號(hào)把終點(diǎn)存到數(shù)組中一個(gè)空的位置，如以編號(hào)為1的起始點(diǎn)：

首先會(huì)把3存到edg[1].edge = 3，且把head數(shù)組中存的最后一個(gè)終點(diǎn)的索引放到其指針域，edge[1].next = head[1]，然后在head數(shù)組里面保存到目前為止起始點(diǎn)1的最后一條邊指向的終點(diǎn)在edg數(shù)組的索引，head[1] = 1；

然后就把編號(hào)2存到edge[2].edge = 2，然后一樣edge[2].next = head[1]，更新最后一條邊的終點(diǎn)的下標(biāo)，head[1] = 2

依此類推…（存一條邊有三步：存編號(hào)->換索引，存編號(hào)edge->留索引next->更新索引head）

存一條邊代碼：

//a為起點(diǎn)編號(hào)，b為終點(diǎn)編號(hào),i為數(shù)組中某個(gè)空的位置的索引
edg[i].edge = b;
edg[i].next = head[a];
head[a] = i

訪問過程：因?yàn)閔ead數(shù)組索引為起點(diǎn)編號(hào)，通過head數(shù)組索引開始訪問。比如訪問起點(diǎn)編號(hào)為5

就會(huì)訪問head[5] 得到一個(gè)值5，然后根據(jù)5這個(gè)這個(gè)值作為一個(gè)索引訪問edg數(shù)組edg[5].edge，得到一個(gè)值4，所以5->4，然后再根據(jù)edg[5].next 得到一個(gè)索引4，然后根據(jù)這個(gè)索引訪問edg[4].edge得到一個(gè)值2，所以5->2,然后再根據(jù)edg[4].next得到一個(gè)-1，如果是-1，說明已經(jīng)是最后一個(gè)了。

依此類推…（訪問都是從head[i]開始，根據(jù)edg[i].next得到下一條邊的終點(diǎn)）

圖示：

代碼演示：

#include<iostream>
#include<cstring>
using namespace std;struct node {int e, v, next;
};int n, m, head[105];
node edg[105];int main() {memset(head, -1, sizeof(head));cin >> n >> m;//n為節(jié)點(diǎn)數(shù)，m為邊數(shù)for (int i = 0; i < m; i++) {int a, b, c;//a為起點(diǎn)編號(hào)，b為終點(diǎn)編號(hào)，c為邊的權(quán)值cin >> a >> b >> c;edg[i].e = b;//任意選一個(gè)空的數(shù)組索引把終點(diǎn)編號(hào)存進(jìn)去edg[i].next = head[a];//把上一個(gè)最后的終點(diǎn)編號(hào)保存到指針域edg[i].v = c;//存權(quán)值head[a] = i;//保存最后一個(gè)的終點(diǎn)在edg數(shù)組中的索引}for (int i = 1; i <= n; i++) {cout << i << ":";for (int j = head[i]; j != -1; j = edg[j].next) {cout << "{" << i << "->" << edg[j].e << "," << edg[j].v << "}";}cout << endl;}return 0;
}

前向星Dijkstra算法：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;struct node {int now, dis;//now為搜索到當(dāng)前節(jié)點(diǎn)的編號(hào)，dis是從原點(diǎn)到此節(jié)點(diǎn)的距離bool operator< (const node &b) const {return this->dis > b.dis;}
};struct edge {int e, v, next;//e為終點(diǎn)編號(hào)，v為權(quán)值，next為下一個(gè)終點(diǎn)的索引
};int n, m, s, ans[200005], head[200005];//n為節(jié)點(diǎn)數(shù)，m為邊數(shù)，s為起點(diǎn)編號(hào)，ans[i]為i編號(hào)節(jié)點(diǎn)的最短距離
edge edg[200005];
int cnt_edge;void add_edge(int a, int b, int c) {edg[cnt_edge].e = b;edg[cnt_edge].v = c;edg[cnt_edge].next = head[a];head[a] = cnt_edge++;
}int main() {memset(head, -1, sizeof(head));memset(ans, 0x3F, sizeof(ans));cin >> n >> m >> s;for (int i = 0; i < m; i++) {int a, b, c;//a為起點(diǎn)，b為終點(diǎn)，c為權(quán)值cin >> a >> b >> c;add_edge(a, b, c);add_edge(b, a, c);}priority_queue<node> que;que.push((node) {s, 0});ans[s] = 0;while (!que.empty()) {node temp = que.top();que.pop();if (ans[temp.now] < temp.dis) {continue;}for (int i = head[temp.now]; i != -1; i = edg[i].next) {//遍歷以temp.now為前驅(qū)節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)int e = edg[i].e, v = edg[i].v;if (ans[e] > temp.dis + v) {ans[e] = temp.dis + v;que.push((node) {e, ans[e]});}}}for (int i = 1; i <= n; i++) {if (ans[i] == 0x3F3F3F3F) {cout << -1 << endl;} else {cout << ans[i] << endl;}}return 0;
}

bellman-ford算法

目的：解決單源最短路徑問題，特殊是可以解決負(fù)數(shù)權(quán)值

bellman-ford算法：暴力，試每一種可能

核心思想：設(shè)s為原點(diǎn)到某節(jié)點(diǎn)的距離，初始化所有節(jié)點(diǎn)的s值為最大值，然后遍歷n（n為節(jié)點(diǎn)數(shù)）遍的m（m為邊數(shù)）遍，也就是以每個(gè)節(jié)點(diǎn)為起始點(diǎn)去進(jìn)行搜索，每一個(gè)節(jié)點(diǎn)都要搜索m遍。

代碼演示：

#include<iostream>
#include<cstring>
using namespace std;struct edge {int s, e, v;
};edge edg[200005];
int n, m, s, edg_cnt, ans[100005];void add_edg(int a, int b, int c) {edg[edg_cnt].s = a;edg[edg_cnt].e = b;edg[edg_cnt++].v = c;
}int main() {memset(ans, 0x3F,sizeof(ans));cin >> n >> m >> s;for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;add_edg(a, b, c);add_edg(b, a, c);}ans[s] = 0;for (int i = 1; i <= n; i++) {for (int j = 0; j < edg_cnt; j++) {int s = edg[j].s, e = edg[j].e, v = edg[j].v;ans[e] = min(ans[e], ans[s] + v);//取終點(diǎn)編號(hào)到原點(diǎn)的距離和當(dāng)前編號(hào)到原點(diǎn)距離加上這條邊的權(quán)值之和中最小的}}for (int i = 1; i <= n; i++) {if (ans[i] == 0x3F3F3F3F) {cout << -1 << endl;} else {cout << ans[i] << endl;}}return 0;
}

基于隊(duì)列優(yōu)化的Ballmen-ford算法（spfa）

由于原本的Ballmen-ford算法中的一些遍歷是多余的，比如如果沒有遍歷靠經(jīng)原點(diǎn)的邊就去遍歷靠后的邊，這樣的遍歷是多余的，因?yàn)橐膊粫?huì)更新。所以引入了隊(duì)列，先遍歷靠前的再遍歷靠后的。

前提：需要一個(gè)隊(duì)列、設(shè)置一個(gè)ans數(shù)組存放最短路徑，一個(gè)mark標(biāo)記數(shù)組，標(biāo)記數(shù)組標(biāo)記的是隊(duì)列中是否存在這個(gè)節(jié)點(diǎn)編號(hào)，入隊(duì)編號(hào)i時(shí)就標(biāo)記mark[i]為1，出隊(duì)就標(biāo)記為0；而且要以某種形式存放每個(gè)起始節(jié)點(diǎn)的終點(diǎn)節(jié)點(diǎn)編號(hào)，可以是靜態(tài)鏈表，也可以是鄰接表，下面代碼以靜態(tài)鏈表為例，所以要構(gòu)造靜態(tài)鏈表就要設(shè)置head數(shù)組和edg數(shù)組，head數(shù)組存放某起始節(jié)點(diǎn)的最后一條終點(diǎn)編號(hào)的所在edg數(shù)的索引。

過程：首先是要有個(gè)原點(diǎn)，在對(duì)隊(duì)列操作前先把原點(diǎn)插入隊(duì)列，然后就可以進(jìn)行隊(duì)列操作了。把隊(duì)首元素彈出，以這個(gè)彈出的元素為一個(gè)起始編號(hào)對(duì)其所有的終點(diǎn)做個(gè)判斷，首先判斷起始節(jié)點(diǎn)編號(hào)對(duì)應(yīng)的最短路徑數(shù)組ans的值加上該起始點(diǎn)到終點(diǎn)的權(quán)值和是否小于終點(diǎn)編號(hào)對(duì)應(yīng)最短路徑數(shù)組ans中的值，如果小于說明這個(gè)路徑更短，就更新終點(diǎn)編號(hào)對(duì)應(yīng)ans中的值；再者，就根據(jù)標(biāo)記數(shù)組判斷隊(duì)列中是否有這個(gè)終點(diǎn)編號(hào)，如果沒有就入隊(duì)。一直操作直到隊(duì)列中沒有元素。

圖解：

代碼演示：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;struct edge {int e, v, next;
};edge edg[200005];
int n, m, s,cnt_edg,  ans[100005], head[100005], mark[100005];void add_edg(int a, int b, int c) {edg[cnt_edg].e = b;edg[cnt_edg].v = c;edg[cnt_edg].next = head[a];head[a] = cnt_edg++;
}int main() {memset(ans, 0x3F, sizeof(ans));memset(head, -1, sizeof(head));cin >> n >> m >> s;for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;add_edg(a, b, c);add_edg(b, a, c);}queue<int> que;que.push(s);ans[s] = 0;while (!que.empty()) {int temp = que.front();que.pop();mark[temp] = 0;for (int i = head[temp]; i != -1; i = edg[i].next) {int e = edg[i].e, v = edg[i].v;if (ans[e] > ans[temp] + v) {ans[e] = ans[temp] + v;if (mark[e] == 0) {mark[e] = 1;que.push(e);}}}}for (int i = 1; i <= n; i++) {if (ans[i] == 0x3F3F3F3F) {cout << - 1 << endl;} else {cout << ans[i] << endl;}}return 0;
}

圖與最短路徑總結(jié)

圖的存儲(chǔ)：鄰接矩陣O(n*n)、鄰接表O(m)、鏈?zhǔn)角跋蛐?m)

最短路徑：floyd(鄰接矩陣)（多源）digkstra（鄰接表，鏈?zhǔn)角跋蛐?#xff09;（）（多源）Ballman-ford（鄰接表，鏈?zhǔn)角跋蛐?#xff09;（單源）spfa（鄰接表，鏈?zhǔn)角跋蛐?#xff09;（單源，負(fù)權(quán)變）

圖論-最小生成樹

圖的最小代價(jià)生成樹

概念：n個(gè)節(jié)點(diǎn)就選n-1條邊，最小生成樹不一定，不一定唯一，不一定不唯一，最小生成樹代價(jià)唯一

Kruskal算法

以邊求解

意義：求解最小生成樹

過程：對(duì)所有邊權(quán)值排序，選出n-1條權(quán)值最小邊，從邊權(quán)值小的遍歷到大的，判斷兩節(jié)點(diǎn)是否相連，如果相連就不選中，否則就是。

圖示：

代碼演示：

#include<iostream>
#include<algorithm>
using namespace std;struct edge {//s為起始點(diǎn)，e為終點(diǎn)，v為權(quán)值，而且重載小于號(hào)為了排序按權(quán)值的大小排序int s, e, v;bool operator< (const edge &b) const {return this->v < b.v;}
};int n, m, ans, cnt, my_union[100005];//n為節(jié)點(diǎn)數(shù)，m為邊數(shù)，my_union數(shù)組為并查集，ans為最小代價(jià)，cnt為邊數(shù)
edge edg[100005];//鄰接表存圖
//初始化并查集，初始每個(gè)節(jié)點(diǎn)間都不相連，為了后面找到樹的邊
void init() {for (int i = 1; i <= n; i++) {my_union[i] = i;}
}//并查集的遍歷，所有節(jié)點(diǎn)的編號(hào)就是并查集的下標(biāo)
int find_fa(int x) {//傳進(jìn)一個(gè)起始點(diǎn)編號(hào)作為下標(biāo)，如果該下索引對(duì)應(yīng)的值就是該索引，說明該索引是該樹干的最后一個(gè)節(jié)點(diǎn)if (my_union[x] == x) {return x;}//如果不是就順著下標(biāo)找，因?yàn)樵谶B接的時(shí)候起始點(diǎn)會(huì)存有該起始點(diǎn)連接的一個(gè)終點(diǎn)編號(hào)對(duì)應(yīng)的值return my_union[x] = find_fa(my_union[x]);
}int main() {cin >> n >> m;for (int i = 0; i< m; i++) {cin >> edg[i].s >> edg[i].e >> edg[i].v;}//初始化并查集init();//排序sort(edg, edg + m);for (int i = 0; i < m; i++) {//分別根據(jù)權(quán)值的小到大在并查集中找起始點(diǎn)和終點(diǎn)是否連接int fa = find_fa(edg[i].s), fb = find_fa(edg[i].e);if (fa != fb) {//如果兩點(diǎn)不連接，就連接my_union[fa] = fb;ans += edg[i].v;//加上代價(jià)cnt++;//樹邊數(shù)加一if (cnt = n - 1) {//如果樹的邊樹夠了說明已經(jīng)生成最小樹，就輸出返回cout << ans << endl;return 0;}}}cout << -1 << endl;return 0;
}

代碼圖解：包括小到大并查集操作和遞歸操作解釋

Prim算法

以點(diǎn)求解最小生成樹

意義：求解最小生成樹

過程：以某個(gè)點(diǎn)為源點(diǎn)，向外擴(kuò)散，每次選一條權(quán)值最小的邊

圖示：

代碼演示：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;//e為終點(diǎn)，v為權(quán)值，并且為了后面的堆排序所以重載小于號(hào)
struct node {int e, v;bool operator< (const node &b) const {return this->v > b.v;}
};//為后面鏈?zhǔn)角跋蛐菧?zhǔn)備
struct edge {int e, v, next;
};edge edg[200005];
int n, m, edg_cnt, ans, mark[100005], cnt, head[100005];//鏈?zhǔn)角跋蛐谴鎴D
void add_edg(int a, int b, int c) {edg[edg_cnt].e = b;edg[edg_cnt].v = c;edg[edg_cnt].next = head[a];head[a] = edg_cnt++;
}int main() {memset(head, -1, sizeof(head));cin >> n >> m;for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;add_edg(a, b, c);add_edg(b, a, c);}priority_queue<node> que;que.push((node){(n / 4 == 0 ? 1 : n / 4), 0});while (!que.empty()) {node temp = que.top();que.pop();//如果彈出的節(jié)點(diǎn)的終點(diǎn)已經(jīng)連接就不再進(jìn)行判斷連接，總結(jié)continueif (mark[temp.e] == 1) {continue;} //如果沒有連接，就把該節(jié)點(diǎn)標(biāo)記為1，意為連接mark[temp.e] = 1;//代價(jià)加上權(quán)值ans += temp.v;//邊數(shù)加一cnt++;//如果已經(jīng)形成樹就返回if (cnt == n - 1) {cout << ans << endl;return 0;}//對(duì)一個(gè)節(jié)點(diǎn)的所以終點(diǎn)進(jìn)行操作，沒有連接就把該終點(diǎn)放到隊(duì)列中for (int i = head[temp.e]; i != -1; i = edg[i].next) {int e = edg[i].e, v= edg[i].v;if (mark[e] == 0) {que.push((node) {e, v});}}}cout << -1 << endl;return 0;
}

圖論-拓?fù)渑判?/h2>

拓?fù)渑判蚯蠼?#xff1a;1、找入度為0的節(jié)點(diǎn) 2、找到該點(diǎn)后，刪除所有以其為起點(diǎn)的邊，刪除其實(shí)就是入度減一。

性質(zhì)：拓?fù)渑判虿晃ㄒ?#xff0c;因?yàn)榭赡芡瑫r(shí)有多個(gè)入度為0的點(diǎn)。

應(yīng)用：判斷圖是否帶環(huán)

代碼演示：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;//用于鏈?zhǔn)角跋蛐谴鎴D
struct edge {int e, next;
};edge edg[1005];
//num數(shù)組保存答案，in_degree數(shù)組統(tǒng)計(jì)入度
int n, m, head[105], num[105], cnt, in_degree[105];int main() {memset(head, -1, sizeof(head));cin >> n >> m;for (int i = 0; i < m; i++) {int a, b;cin >> a >> b;in_degree[b]++;//計(jì)數(shù)入度edg[i].e = b;edg[i].next = head[a];head[a] = i;}//queue<int> que;priority_queue<int, vector<int>, greater<int>> que;//因?yàn)橥負(fù)渑判蛴卸鄠€(gè)結(jié)果，所以為了從小到大就用一個(gè)小頂堆//隊(duì)列que保存所有入度為0的元素for (int i = 1; i <= n; i++) {if (in_degree[i] == 0) {que.push(i);}}while (!que.empty()) {int temp = que.top();que.pop();//計(jì)數(shù)存答案num[cnt++] = temp;//對(duì)每個(gè)終點(diǎn)的入度減一，如果該入度為0就入隊(duì)，否則就不需要入隊(duì)for (int i = head[temp]; i != -1; i = edg[i].next) {int e = edg[i].e;in_degree[e]--;if (in_degree[e] == 0) {que.push(e);}}}//如果是環(huán)就輸出no，因?yàn)橛协h(huán)就不能把所有的節(jié)點(diǎn)都入隊(duì)一遍，所以肯定小于節(jié)點(diǎn)數(shù)if (cnt != n ) {cout << "no" << endl;return 0;}//否則輸出這個(gè)順序for (int i = 0; i < cnt; i++) {i && cout << " ";cout << num[i] << " ";}cout << endl;return 0;}

輸出所有拓?fù)渑判?#xff1a;

#include<iostream>
#include<vector>
using namespace std;int n, m, f, num[105], in_degree[105], mark[105];void func(int now, vector<vector<int> > &edg) {if (now == n + 1) {//當(dāng)遞歸到最后一個(gè)節(jié)點(diǎn)就輸出for (int i = 1; i <= n; i++) {cout << num[i] << " ";}cout << endl;f = 1;return ;}for (int i = 1; i <= n; i++) {//遍歷每個(gè)節(jié)點(diǎn)編號(hào)if (in_degree[i] == 0 && mark[i] == 0) {//入度為0且沒有遍歷過就進(jìn)行遍歷num[now] = i;mark[i] = 1; for (int j = 0; j < edg[i].size(); j++) {//把當(dāng)前起點(diǎn)的所有的終點(diǎn)的入度減一in_degree[edg[i][j]]--;}func(now + 1, edg);//在遞歸過程會(huì)不斷地對(duì)入度減一直到最后一個(gè)節(jié)點(diǎn)遍歷完。比如最后一層輸出完畢后就會(huì)執(zhí)行以下代碼，把標(biāo)記還原，把入度還原，這就是搜索回溯，回到前一個(gè)度數(shù)多的一個(gè)節(jié)點(diǎn)mark[i] = 0;for (int j = 0; j < edg[i].size(); j++) {in_degree[edg[i][j]]++;}}}
}int main() {cin >> n >> m;vector<vector<int> > edg(n + 1, vector<int>());for (int i = 0; i < m; i++) {int a, b;cin >> a >> b;in_degree[b]++;edg[a].push_back(b);}func(1, edg);if (f == 0) {cout << "no" << endl;}return 0;
}