圖論入門與最短路徑算法

圖的基本概念

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

圖的一些概念：

①有向邊（有向圖），無向邊（無向圖），權值

②節(jié)點（度），對應無向圖，度就是節(jié)點連著幾條邊，對于有向圖就是出度加入度

③完全連通圖

④子圖

⑤路徑

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

圖的遍歷：

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

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

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

圖的存儲：

鄰接矩陣

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

設兩點連通為1

如果有權值

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

缺點：存儲了一些無用信息，浪費空間；不能快速地訪問以某點為起點的所有的邊。

代碼演示：

#include<iostream>
using namespace std;int n, m, arr[105][105];int main() {cin >> n >> m;//n為節(jié)點個數//m為邊的個數，每條邊帶一個權值，一個循環(huán)把權值存到數組里面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算法

算法解決問題：多源（多個原點）最短路徑問題

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

核心思想圖示：以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]為經過i點中轉，從j到i再到k。注意，無論之間有多少個中轉點，每三個都會被合并為一個，比如15234，合并523后會變成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++) {//全邊（保留權值最小的邊）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]為經過i點中轉，從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;}

鄰接表

鄰接表：構建一個列數可變的二維數組，根據節(jié)點數定義定義行數

鄰接表的優(yōu)缺點和鄰接矩陣的優(yōu)缺點互補

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

缺點：①不能快速判斷兩點間的關系

代碼演示：

基礎理解代碼：

#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為起點節(jié)點，b為終點節(jié)點，c為權值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;
//保存終點節(jié)點和此路徑的權值，也可用鍵值對來保存
struct edge {int e, v;
};int main() {int n, m;cin >> n >> m;//n為節(jié)點數，m為邊數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為起點節(jié)點，b為終點節(jié)點，c為權值}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算法

算法解決問題：解決單源（一個原點）最短路徑的問題

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

核心思想：

用一個數組保存一個能到此節(jié)點的所有的距離

核心思想圖示：

代碼演示：

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

鏈式前向星

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

鏈式前向星=>采取頭插法的靜態(tài)鏈表

意義：保存每兩個有聯系點

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

保存過程：首先根據一個起始點的編號把終點存到數組中一個空的位置，如以編號為1的起始點：

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

然后就把編號2存到edge[2].edge = 2，然后一樣edge[2].next = head[1]，更新最后一條邊的終點的下標，head[1] = 2

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

存一條邊代碼：

//a為起點編號，b為終點編號,i為數組中某個空的位置的索引
edg[i].edge = b;
edg[i].next = head[a];
head[a] = i

訪問過程：因為head數組索引為起點編號，通過head數組索引開始訪問。比如訪問起點編號為5

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

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

圖示：

代碼演示：

#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é)點數，m為邊數for (int i = 0; i < m; i++) {int a, b, c;//a為起點編號，b為終點編號，c為邊的權值cin >> a >> b >> c;edg[i].e = b;//任意選一個空的數組索引把終點編號存進去edg[i].next = head[a];//把上一個最后的終點編號保存到指針域edg[i].v = c;//存權值head[a] = i;//保存最后一個的終點在edg數組中的索引}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為搜索到當前節(jié)點的編號，dis是從原點到此節(jié)點的距離bool operator< (const node &b) const {return this->dis > b.dis;}
};struct edge {int e, v, next;//e為終點編號，v為權值，next為下一個終點的索引
};int n, m, s, ans[200005], head[200005];//n為節(jié)點數，m為邊數，s為起點編號，ans[i]為i編號節(jié)點的最短距離
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為起點，b為終點，c為權值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為前驅節(jié)點的所有后繼節(jié)點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算法

目的：解決單源最短路徑問題，特殊是可以解決負數權值

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

核心思想：設s為原點到某節(jié)點的距離，初始化所有節(jié)點的s值為最大值，然后遍歷n（n為節(jié)點數）遍的m（m為邊數）遍，也就是以每個節(jié)點為起始點去進行搜索，每一個節(jié)點都要搜索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);//取終點編號到原點的距離和當前編號到原點距離加上這條邊的權值之和中最小的}}for (int i = 1; i <= n; i++) {if (ans[i] == 0x3F3F3F3F) {cout << -1 << endl;} else {cout << ans[i] << endl;}}return 0;
}

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

由于原本的Ballmen-ford算法中的一些遍歷是多余的，比如如果沒有遍歷靠經原點的邊就去遍歷靠后的邊，這樣的遍歷是多余的，因為也不會更新。所以引入了隊列，先遍歷靠前的再遍歷靠后的。

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

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

圖解：

代碼演示：

#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;
}

圖與最短路徑總結

圖的存儲：鄰接矩陣O(n*n)、鄰接表O(m)、鏈式前向星(m)

最短路徑：floyd(鄰接矩陣)（多源）digkstra（鄰接表，鏈式前向星）（）（多源）Ballman-ford（鄰接表，鏈式前向星）（單源）spfa（鄰接表，鏈式前向星）（單源，負權變）

圖論-最小生成樹

圖的最小代價生成樹

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

Kruskal算法

以邊求解

意義：求解最小生成樹

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

圖示：

代碼演示：

#include<iostream>
#include<algorithm>
using namespace std;struct edge {//s為起始點，e為終點，v為權值，而且重載小于號為了排序按權值的大小排序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é)點數，m為邊數，my_union數組為并查集，ans為最小代價，cnt為邊數
edge edg[100005];//鄰接表存圖
//初始化并查集，初始每個節(jié)點間都不相連，為了后面找到樹的邊
void init() {for (int i = 1; i <= n; i++) {my_union[i] = i;}
}//并查集的遍歷，所有節(jié)點的編號就是并查集的下標
int find_fa(int x) {//傳進一個起始點編號作為下標，如果該下索引對應的值就是該索引，說明該索引是該樹干的最后一個節(jié)點if (my_union[x] == x) {return x;}//如果不是就順著下標找，因為在連接的時候起始點會存有該起始點連接的一個終點編號對應的值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++) {//分別根據權值的小到大在并查集中找起始點和終點是否連接int fa = find_fa(edg[i].s), fb = find_fa(edg[i].e);if (fa != fb) {//如果兩點不連接，就連接my_union[fa] = fb;ans += edg[i].v;//加上代價cnt++;//樹邊數加一if (cnt = n - 1) {//如果樹的邊樹夠了說明已經生成最小樹，就輸出返回cout << ans << endl;return 0;}}}cout << -1 << endl;return 0;
}

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

Prim算法

以點求解最小生成樹

意義：求解最小生成樹

過程：以某個點為源點，向外擴散，每次選一條權值最小的邊

圖示：

代碼演示：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;//e為終點，v為權值，并且為了后面的堆排序所以重載小于號
struct node {int e, v;bool operator< (const node &b) const {return this->v > b.v;}
};//為后面鏈式前向星準備
struct edge {int e, v, next;
};edge edg[200005];
int n, m, edg_cnt, ans, mark[100005], cnt, head[100005];//鏈式前向星存圖
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é)點的終點已經連接就不再進行判斷連接，總結continueif (mark[temp.e] == 1) {continue;} //如果沒有連接，就把該節(jié)點標記為1，意為連接mark[temp.e] = 1;//代價加上權值ans += temp.v;//邊數加一cnt++;//如果已經形成樹就返回if (cnt == n - 1) {cout << ans << endl;return 0;}//對一個節(jié)點的所以終點進行操作，沒有連接就把該終點放到隊列中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;
}

圖論-拓撲排序

拓撲排序求解：1、找入度為0的節(jié)點 2、找到該點后，刪除所有以其為起點的邊，刪除其實就是入度減一。

性質：拓撲排序不唯一，因為可能同時有多個入度為0的點。

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

代碼演示：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;//用于鏈式前向星存圖
struct edge {int e, next;
};edge edg[1005];
//num數組保存答案，in_degree數組統(tǒng)計入度
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]++;//計數入度edg[i].e = b;edg[i].next = head[a];head[a] = i;}//queue<int> que;priority_queue<int, vector<int>, greater<int>> que;//因為拓撲排序有多個結果，所以為了從小到大就用一個小頂堆//隊列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();//計數存答案num[cnt++] = temp;//對每個終點的入度減一，如果該入度為0就入隊，否則就不需要入隊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，因為有環(huán)就不能把所有的節(jié)點都入隊一遍，所以肯定小于節(jié)點數if (cnt != n ) {cout << "no" << endl;return 0;}//否則輸出這個順序for (int i = 0; i < cnt; i++) {i && cout << " ";cout << num[i] << " ";}cout << endl;return 0;}

輸出所有拓撲排序：

#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) {//當遞歸到最后一個節(jié)點就輸出for (int i = 1; i <= n; i++) {cout << num[i] << " ";}cout << endl;f = 1;return ;}for (int i = 1; i <= n; i++) {//遍歷每個節(jié)點編號if (in_degree[i] == 0 && mark[i] == 0) {//入度為0且沒有遍歷過就進行遍歷num[now] = i;mark[i] = 1; for (int j = 0; j < edg[i].size(); j++) {//把當前起點的所有的終點的入度減一in_degree[edg[i][j]]--;}func(now + 1, edg);//在遞歸過程會不斷地對入度減一直到最后一個節(jié)點遍歷完。比如最后一層輸出完畢后就會執(zhí)行以下代碼，把標記還原，把入度還原，這就是搜索回溯，回到前一個度數多的一個節(jié)點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;
}