以下總結(jié)摘自y總

目錄

• DFS和BFS
• 樹(shù)與圖的存儲(chǔ)
• 樹(shù)與圖的遍歷
• 拓?fù)渑判?/li>
• 樸素dijkstra算法
• 堆優(yōu)化版dijkstra
• Bellman-Ford算法
• spfa 算法（隊(duì)列優(yōu)化的Bellman-Ford算法）
• spfa判斷圖中是否存在負(fù)環(huán)
• floyd算法
• 樸素版prim算法
• Kruskal算法
• 染色法判別二分圖
• 匈牙利算法 (二分圖匹配)

DFS和BFS

842. 排列數(shù)字
843. n-皇后問(wèn)題
844. 走迷宮
845. 八數(shù)碼

樹(shù)與圖的存儲(chǔ)

樹(shù)是一種特殊的圖，與圖的存儲(chǔ)方式相同。
對(duì)于無(wú)向圖中的邊ab，存儲(chǔ)兩條有向邊a->b, b->a。
因此我們可以只考慮有向圖的存儲(chǔ)。

(1) 鄰接矩陣：g[a][ b ] 存儲(chǔ)邊a->b

(2) 鄰接表：

有向圖的鄰接表存儲(chǔ)就是對(duì)于每個(gè)點(diǎn) v 對(duì)應(yīng)一個(gè)頭節(jié)點(diǎn), 記錄在h[v] idx是圖里邊的編號(hào)，和建圖的順序有關(guān)，對(duì)于某一個(gè)點(diǎn)v, 它的所有鄰邊的編號(hào)不一定是連續(xù)的。 e 數(shù)組是edge的縮寫(xiě)，記錄了某一條有向邊的終點(diǎn) ne數(shù)組是next的縮寫(xiě)，記錄了鄰接表里的同一個(gè)點(diǎn)的下一條鄰邊的idx ne[idx]=h[a]; h[a]=idx; 就是把新建的邊插入隊(duì)頭。(先把新建的邊的next指向現(xiàn)在隊(duì)頭的next，然后更新隊(duì)頭的next） 然后再idx++, 給下一次建邊使用 // 對(duì)于每個(gè)點(diǎn)k，開(kāi)一個(gè)單鏈表，存儲(chǔ)k所有可以走到的點(diǎn)。h[k]存儲(chǔ)這個(gè)單鏈表的頭結(jié)點(diǎn) int h[N], e[N], ne[N], idx;// 添加一條邊a->b void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }// 初始化 idx = 0; memset(h, -1, sizeof h);

樹(shù)與圖的遍歷

時(shí)間復(fù)雜度 O(n+m), n 表示點(diǎn)數(shù)，m 表示邊數(shù)
(1) 深度優(yōu)先遍歷 —— 模板題 AcWing 846. 樹(shù)的重心

int dfs(int u) {st[u] = true; // st[u] 表示點(diǎn)u已經(jīng)被遍歷過(guò)for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (!st[j]) dfs(j);} }

(2) 寬度優(yōu)先遍歷 —— 模板題 AcWing 847. 圖中點(diǎn)的層次

queue<int> q; st[1] = true; // 表示1號(hào)點(diǎn)已經(jīng)被遍歷過(guò) q.push(1);while (q.size()) {int t = q.front();q.pop();for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (!st[j]){st[j] = true; // 表示點(diǎn)j已經(jīng)被遍歷過(guò)q.push(j);}} }

拓?fù)渑判?/h1>

模板題 AcWing 848. 有向圖的拓?fù)湫蛄?br /> 時(shí)間復(fù)雜度 O(n+m), n 表示點(diǎn)數(shù)，m 表示邊數(shù)

bool topsort() {int hh = 0, tt = -1;// d[i] 存儲(chǔ)點(diǎn)i的入度for (int i = 1; i <= n; i ++ )if (!d[i])q[ ++ tt] = i;while (hh <= tt){int t = q[hh ++ ];for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (-- d[j] == 0)q[ ++ tt] = j;}}// 如果所有點(diǎn)都入隊(duì)了，說(shuō)明存在拓?fù)湫蛄?#xff1b;否則不存在拓?fù)湫蛄小?/span>return tt == n - 1; }

樸素dijkstra算法

模板題 AcWing 849. Dijkstra求最短路 I

時(shí)間復(fù)雜是 O(n²+m), n表示點(diǎn)數(shù)，m 表示邊數(shù)

int g[N][N]; // 存儲(chǔ)每條邊 int dist[N]; // 存儲(chǔ)1號(hào)點(diǎn)到每個(gè)點(diǎn)的最短距離 bool st[N]; // 存儲(chǔ)每個(gè)點(diǎn)的最短路是否已經(jīng)確定// 求1號(hào)點(diǎn)到n號(hào)點(diǎn)的最短路，如果不存在則返回-1 int dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < n - 1; i ++ ){int t = -1; // 在還未確定最短路的點(diǎn)中，尋找距離最小的點(diǎn)for (int j = 1; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;// 用t更新其他點(diǎn)的距離for (int j = 1; j <= n; j ++ )dist[j] = min(dist[j], dist[t] + g[t][j]);st[t] = true;}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n]; }

堆優(yōu)化版dijkstra

模板題 AcWing 850. Dijkstra求最短路 II
時(shí)間復(fù)雜度 O(mlogn), n 表示點(diǎn)數(shù)，m 表示邊數(shù)

typedef pair<int, int> PII;int n; // 點(diǎn)的數(shù)量 int h[N], w[N], e[N], ne[N], idx; // 鄰接表存儲(chǔ)所有邊 int dist[N]; // 存儲(chǔ)所有點(diǎn)到1號(hào)點(diǎn)的距離 bool st[N]; // 存儲(chǔ)每個(gè)點(diǎn)的最短距離是否已確定// 求1號(hào)點(diǎn)到n號(hào)點(diǎn)的最短距離，如果不存在，則返回-1 int dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1}); // first存儲(chǔ)距離，second存儲(chǔ)節(jié)點(diǎn)編號(hào) //因?yàn)橐揖嚯x源點(diǎn)最近的點(diǎn)，而pair默認(rèn)先按第一關(guān)鍵字排再按第二關(guān)鍵字排while (heap.size()){auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if (st[ver]) continue;st[ver] = true;for (int i = h[ver]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > distance + w[i]) // w[i] 切記{dist[j] = distance + w[i];heap.push({dist[j], j});}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n]; }

Bellman-Ford算法

模板題 AcWing 853. 有邊數(shù)限制的最短路
時(shí)間復(fù)雜度 O(nm), n 表示點(diǎn)數(shù)，m 表示邊數(shù)

上圖摘自小呆呆大神 :https://www.acwing.com/solution/content/6320/

backup就相當(dāng)于，我們bfs()四個(gè)方向枚舉的時(shí)候，是用當(dāng)前點(diǎn)枚舉的，
不能走一個(gè)方向后，用新的點(diǎn)接著串聯(lián)枚舉。

const int N=510; const int M=1e4+10;int n, m; // n表示點(diǎn)數(shù)，m表示邊數(shù) int dist[N],backup[N]; // dist[x]存儲(chǔ)1到x的最短路距離struct Edge // 邊，a表示出點(diǎn)，b表示入點(diǎn)，w表示邊的權(quán)重 {int a, b, w; }edges[M];// 求1到n的最短路距離，如果無(wú)法從1走到n，則返回-1。 int bellman_ford() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;// 如果第n次迭代仍然會(huì)松弛三角不等式，就說(shuō)明存在一條長(zhǎng)度是n+1的最短路徑，//由抽屜原理，路徑中至少存在兩個(gè)相同的點(diǎn)，說(shuō)明圖中存在負(fù)權(quán)回路。for (int i = 0; i < n; i ++ ){memcpy(backup,dist,sizeof dist);for (int j = 0; j < m; j ++ ){int a = edges[j].a, b = edges[j].b, w = edges[j].w;dist[b]=min(dist[b],backup[a]+w);}}if (dist[n] > 0x3f3f3f3f / 2) return -1;return dist[n]; }

spfa 算法（隊(duì)列優(yōu)化的Bellman-Ford算法）

模板題 AcWing 851. spfa求最短路
時(shí)間復(fù)雜度 平均情況下 O(m)，最壞情況下 O(nm), n 表示點(diǎn)數(shù)，m 表示邊數(shù)
Bellman_ford算法會(huì)遍歷所有的邊，但是有很多的邊遍歷了其實(shí)沒(méi)有什么意義，
我們只用遍歷那些到源點(diǎn)距離變小的點(diǎn)所連接的邊即可，
只有當(dāng)一個(gè)點(diǎn)的前驅(qū)結(jié)點(diǎn)更新了，該節(jié)點(diǎn)才會(huì)得到更新；
因此考慮到這一點(diǎn)，我們將創(chuàng)建一個(gè)隊(duì)列每一次加入距離被更新的結(jié)點(diǎn)。



上圖摘自:
小呆呆：https://www.acwing.com/solution/content/6325/
orzorz: https://www.acwing.com/solution/content/9306/

int n; // 總點(diǎn)數(shù) int h[N], w[N], e[N], ne[N], idx; // 鄰接表存儲(chǔ)所有邊 int dist[N]; // 存儲(chǔ)每個(gè)點(diǎn)到1號(hào)點(diǎn)的最短距離 bool st[N]; // 存儲(chǔ)每個(gè)點(diǎn)是否在隊(duì)列中// 求1號(hào)點(diǎn)到n號(hào)點(diǎn)的最短路距離，如果從1號(hào)點(diǎn)無(wú)法走到n號(hào)點(diǎn)則返回-1 int spfa() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q;q.push(1);st[1] = true;//標(biāo)記入隊(duì)了while (q.size()){auto t = q.front();q.pop();st[t] = false;//標(biāo)記出隊(duì)了for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if (!st[j]) // 如果隊(duì)列中已存在j，則不需要將j重復(fù)插入{q.push(j);st[j] = true;}}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n]; }

spfa判斷圖中是否存在負(fù)環(huán)

模板題 AcWing 852. spfa判斷負(fù)環(huán)
時(shí)間復(fù)雜度是 O(nm), n 表示點(diǎn)數(shù)，m 表示邊數(shù)

int n; // 總點(diǎn)數(shù) int h[N], w[N], e[N], ne[N], idx; // 鄰接表存儲(chǔ)所有邊 int dist[N], cnt[N]; // dist[x]存儲(chǔ)1號(hào)點(diǎn)到x的最短距離，cnt[x]存儲(chǔ)1到x的最短路中經(jīng)過(guò)的點(diǎn)數(shù) bool st[N]; // 存儲(chǔ)每個(gè)點(diǎn)是否在隊(duì)列中// 如果存在負(fù)環(huán)，則返回true，否則返回false。 bool spfa() {// 不需要初始化dist數(shù)組// 原理：如果某條最短路徑上有n個(gè)點(diǎn)（除了自己），那么加上自己之后一共有n+1個(gè)點(diǎn)，由抽屜原理一定有兩個(gè)點(diǎn)相同，所以存在環(huán)。queue<int> q;for (int i = 1; i <= n; i ++ ){q.push(i);st[i] = true;}while (q.size()){auto t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];cnt[j] = cnt[t] + 1;if (cnt[j] >= n) return true; // 如果從1號(hào)點(diǎn)到x的最短路中包含至少n個(gè)點(diǎn)（不包括自己），則說(shuō)明存在環(huán)if (!st[j]){q.push(j);st[j] = true;}}}}return false; }

floyd算法

模板題 AcWing 854. Floyd求最短路
時(shí)間復(fù)雜度是 O(n³), n 表示點(diǎn)數(shù)

摘自:小呆呆 https://www.acwing.com/solution/content/6337/

初始化：for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (i == j) d[i][j] = 0;else d[i][j] = INF;// 算法結(jié)束后，d[a][b]表示a到b的最短距離 void floyd() {for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }

樸素版prim算法

模板題 AcWing 858. Prim算法求最小生成樹(shù)
時(shí)間復(fù)雜度是 O(n²+m), n 表示點(diǎn)數(shù)，m 表示邊數(shù)

int n; // n表示點(diǎn)數(shù) int g[N][N]; // 鄰接矩陣，存儲(chǔ)所有邊 int dist[N]; // 存儲(chǔ)其他點(diǎn)到當(dāng)前最小生成樹(shù)的距離 bool st[N]; // 存儲(chǔ)每個(gè)點(diǎn)是否已經(jīng)在生成樹(shù)中// 如果圖不連通，則返回INF(值是0x3f3f3f3f), 否則返回最小生成樹(shù)的樹(shù)邊權(quán)重之和 int prim() {memset(dist, 0x3f, sizeof dist);int res = 0;for (int i = 0; i < n; i ++ ){int t = -1;for (int j = 1; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;if (i && dist[t] == INF) return INF; //說(shuō)明不連通if (i) res += dist[t]; //第一次迭代也就是第一個(gè)點(diǎn)的距離不用加st[t] = true;for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);}return res; }

Kruskal算法

模板題 AcWing 859. Kruskal算法求最小生成樹(shù)
時(shí)間復(fù)雜度是 O(mlogm), n 表示點(diǎn)數(shù)，m 表示邊數(shù)

int n, m; // n是點(diǎn)數(shù)，m是邊數(shù) int p[N]; // 并查集的父節(jié)點(diǎn)數(shù)組struct Edge // 存儲(chǔ)邊 {int a, b, w;bool operator< (const Edge &W)const{return w < W.w;} }edges[M];int find(int x) // 并查集核心操作 {if (p[x] != x) p[x] = find(p[x]);return p[x]; }int kruskal() {sort(edges, edges + m);for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集int res = 0, cnt = 0;for (int i = 0; i < m; i ++ ){int a = edges[i].a, b = edges[i].b, w = edges[i].w;a = find(a), b = find(b);if (a != b) // 如果兩個(gè)連通塊不連通，則將這兩個(gè)連通塊合并{p[a] = b;res += w;cnt ++ ;}}if (cnt < n - 1) return INF;return res; }

染色法判別二分圖

模板題 AcWing 860. 染色法判定二分圖
時(shí)間復(fù)雜度是 O(n+m), n 表示點(diǎn)數(shù)，m 表示邊數(shù)

int n; // n表示點(diǎn)數(shù) int h[N], e[M], ne[M], idx; // 鄰接表存儲(chǔ)圖 int color[N]; // 表示每個(gè)點(diǎn)的顏色，-1表示未染色，0表示白色，1表示黑色// 參數(shù)：u表示當(dāng)前節(jié)點(diǎn)，c表示當(dāng)前點(diǎn)的顏色 bool dfs(int u, int c) {color[u] = c;for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (color[j] == -1){if (!dfs(j, !c)) return false; //染色沖突了}else if (color[j] == c) return false;//染色沖突了}return true; }bool check() {memset(color, -1, sizeof color);bool flag = true;for (int i = 1; i <= n; i ++ )if (color[i] == -1)if (!dfs(i, 0)){flag = false;break;}return flag; }

匈牙利算法 (二分圖匹配)

模板題 AcWing 861. 二分圖的最大匹配
時(shí)間復(fù)雜度是 O(nm), n 表示點(diǎn)數(shù)，m 表示邊數(shù)

int n1, n2; // n1表示第一個(gè)集合中的點(diǎn)數(shù)，n2表示第二個(gè)集合中的點(diǎn)數(shù) int h[N], e[M], ne[M], idx; // 鄰接表存儲(chǔ)所有邊，匈牙利算法中只會(huì)用到從第一個(gè)集合指向第二個(gè)集合的邊，所以這里只用存一個(gè)方向的邊 int match[N]; // 存儲(chǔ)第二個(gè)集合中的每個(gè)點(diǎn)當(dāng)前匹配的第一個(gè)集合中的點(diǎn)是哪個(gè) bool st[N]; // 表示第二個(gè)集合中的每個(gè)點(diǎn)是否已經(jīng)被遍歷過(guò)bool find(int x) {for (int i = h[x]; i != -1; i = ne[i]){int j = e[i];if (!st[j]){st[j] = true;if (match[j] == 0 || find(match[j])){match[j] = x;return true;}}}return false; }// 求最大匹配數(shù)，依次枚舉第一個(gè)集合中的每個(gè)點(diǎn)能否匹配第二個(gè)集合中的點(diǎn) int res = 0; for (int i = 1; i <= n1; i ++ ) {memset(st, false, sizeof st);if (find(i)) res ++ ; }

總結(jié)

以上是生活随笔為你收集整理的第三章 搜索与图论 【完结】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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