基本概念
樹（Tree）
如果一個無向連通圖中不存在回路，則這種圖稱為樹，
生成樹 （Spanning Tree）
無向連通圖G的一個子圖如果是一顆包含G的所有頂點的樹，則該子圖稱為G的生成樹，
生成樹是連通圖的極小連通子圖，這里所謂極小是指：若在樹中任意增加一條邊，則將出現一潭訓路；若去掉一條邊，將會使之變成非連通圖，
最小生成樹
一個帶權值的連通圖，用$n-1$條邊把$n$個頂點連接起來，且連接起來的權值最小，
應用場景
設想有9個村莊，這些村莊構成如下圖所示的地理位置，每個村莊的直線距離都不一樣，若要在每個村莊間架設網路線纜，若要保證成本最小，則需要選擇一條能夠聯通9個村莊，且長度最小的路線，
Kruskal演算法
知識點：資料結構——并查集
基本思想
始終選擇當前可用、不會（和已經選取的邊）構成回路的最小權植邊，
具體步驟：
1. 將所有邊按權值進行升序排序
2. 依次選擇權值最小的邊
3. 若該邊的兩個頂點落在不同的連通分量上，選擇這條邊，并把這兩個頂點標記為同一連通分量；若這條邊的兩個頂點落到同一連通分量上，舍棄這條邊，反復執行2,3，直到所有的都在同一連通分量上，【這一步需要用到上面的并查集】
模板題：https://www.luogu.org/problem/P3366
#include <iostream> #include <algorithm> using namespace std; int pre[5005]; int n, m; //n個定點，m條邊 struct ENode { int from, to, dis; bool operator<(ENode p) { return dis < p.dis; } }M[200005]; int Find(int x) { return x == pre[x] ? pre[x] : pre[x] = Find(pre[x]); } int kurskal() { sort(M, M + m); int N = n, res = 0; for (int i = 0; i < m && N > 1; i++) { int fx = Find(M[i].from), fy = Find(M[i].to); if (fx != fy) { pre[fx] = fy; N--;//找到了一條邊，當N減到1的時候表明已經找到N-1條邊了，就完成了 res += M[i].dis; } } if (N == 1)//回圈做完，N不等于1 表明沒有找到合適的N-1條邊來構成最小生成樹 return res; return -1; } int main() { cin >> n >> m; for (int i = 0; i <= n; i++) { pre[i] = i; } for (int i = 0; i < m; i++) { scanf("%d%d%d", &M[i].from, &M[i].to, &M[i].dis);; } int ans = kurskal(); if (ans != -1) cout << ans << endl; else cout << "orz" << endl; return 0; }
Prim演算法
Prim演算法思想：
首先將圖的點分為兩部分，一種是訪問過的$u$（第一條邊任選），一種是沒有訪問過的$v$
1: 每次找$u$到$v$的權值最小的邊，
2: 然后將這條邊中的$v$中的頂點添加到$u$中，直到$v$中邊的個數$=$頂點數$-1$
圖解步驟：
維護一個$dis$陣列，記錄只使用已訪問節點能夠到達各未訪問節點最短的權值，
初始值為節點1（任意一個都可以）到各點的值，規定到自己是0，到不了的是$inf$（定義一個特別大的數），
找當前能到達的權值最短的點，1-->4，節點4
將dis[4]賦值為0，標記為已訪問過，同時借助4節點更新dis陣列，
后面依次
最后整個dis陣列都是0了，最小生成樹也就出來了，如果$dis$陣列中還有 $inf$ 的話，說明這不是一個連通圖，
還是上面那道模板題：https://www.luogu.org/problem/P3366
#include <iostream> #include <fstream> using namespace std; struct ENode { int dis, to;//權重、指向 ENode* next = NULL; void push(int to, int dis) { ENode* p = new ENode; p->to = to; p->dis = dis; p->next = next; next = p; } }*head; const int inf = 1 << 30; int N, M; int dis[5005]; int prim() { int res = 0; for (int i = 2; i <= N; i++) { dis[i] = inf; } for (int i = 0; i < N; i++) {//與kurskal區分，找邊是N-1條邊，找點是N個點 int v = 1 , MIN = inf; for (int j = 1; j <= N; j++) { //到不了的，訪問過的不進行比較 if (dis[j] != 0 && dis[j] < MIN) { v = j; MIN = dis[j]; } } if (MIN == inf && v != 1)//這里v!=1是為了把dis的初始化放在回圈里面做，也可以放在回圈外面做，但是外層回圈就只需要做N-1次了 return -1;//還沒找夠n個點，沒路了 res += dis[v]; dis[v] = 0; ENode *p = head[v].next; while (p) { if (dis[p->to] > p->dis) { dis[p->to] = p->dis; } p = p->next; } } return res; } int main() { #ifdef LOCAL fstream cin("data.in"); #endif // LOCAL cin >> N >> M; head = new ENode[N + 1]; for (int i = 0; i < M; i++) { int from, to, dis; scanf("%d%d%d", &from, &to, &dis); //cin >> from >> to >> dis; head[from].push(to, dis); head[to].push(from, dis); } int ans = prim(); if (ans != -1) cout << ans << endl; else cout << "orz" << endl; return 0; }
兩者區別
時間復雜度
prim演算法
時間復雜度為$O(n^2)$，$n$為頂點的數量，其時間復雜度與邊得數目無關，適合稠密圖，
kruskal演算法
時間復雜度為$O(e\cdot loge)$，$e$為邊的數目，與頂點數量無關，適合稀疏圖，
其實就是排序的時間，因為并查集的查詢、合并操作都是$O(1)$，
總結
通俗點說就是，點多邊少用Kruskal，因為Kruskal演算法每次查找最短的邊， 點少邊多用Prim，因為它是每次找一個頂點，
具體選擇用那個，可以用電腦算一下，題目給的資料級別，$n^2$和$e\cdot loge$看看那個小，比如上面的模板題，題目給的資料級別是$(n<=5000,e<=200000)$，粗略估算一下，kurskal演算法一定是會快不少的，結果也確實如粗，
實作難度
明眼人都能看出來，kurskal演算法要簡單太多了，kurskal演算法不需要把圖表示出來，而Prim演算法必須建表或者鄰接矩陣，所以從上面的資料也能看出來當邊的數目較大時，Prim演算法所占用的空間比kurskal演算法多了很多，
拓展
堆優化Prim演算法
用堆存盤當前所有可到達的點和距離，就是把dis陣列里的內容一式兩份，存在堆里，然后每次取堆頂元素，每次操作為$O(logn)$，所以使用堆優化后的Prim演算法理論上時間復雜度為$O(nlogn)$，但是好像沒有達到想要的效果
看了測驗資料發現，有很多重邊，那就合理了，做了很多次的無用回圈，所以時間上也和kurskal比較相近，所以在資料可靠、無重邊的情況下，這個演算法一定是上述幾種中最快的一個，
#include <iostream> #include <fstream> #include <cstdio> #include <queue> using namespace std; struct P { int dis, v; P(int d, int v) :dis(d), v(v) {}; bool operator<(P p)const { return p.dis < dis; } }; struct ENode { int dis, to;//權重、指向 ENode* next = NULL; void push(int to, int dis) { ENode* p = new ENode; p->to = to; p->dis = dis; p->next = next; next = p; } }*head; const int inf = 1 << 30; int N, M; int dis[5005]; bool fuck[5005]; int prim() { priority_queue<P>pq; pq.push(P(0, 1)); int res = 0, cnt = N; dis[1] = 0; fill(dis + 1, dis + N + 1, inf); while (!pq.empty() && cnt > 0) {//與kurskal區分，找邊是N-1條邊，找點是N個點 int v = pq.top().v, d = pq.top().dis; pq.pop(); if (fuck[v])continue; fuck[v] = true; res += d; cnt--; ENode* p = head[v].next; while (p) { if (dis[p->to] > p->dis) { dis[p->to] = p->dis; pq.push(P(p->dis, p->to)); } p = p->next; } } if (cnt > 1) return -1; return res; } int main() { #ifdef LOCAL fstream cin("data.in"); #endif // LOCAL cin >> N >> M; head = new ENode[N + 1]; for (int i = 0; i < M; i++) { int from, to, dis; scanf("%d%d%d", &from, &to, &dis); //cin >> from >> to >> dis; head[from].push(to, dis); head[to].push(from, dis); } int ans = prim(); if (ans != -1) cout << ans << endl; else cout << "orz" << endl; return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137723.html
標籤：其他
上一篇：圖論篇1——圖的基本概念
下一篇：獲取陣列中所有重復的元素