今天復習最小生成樹演算法，
最小生成樹指的是在一個圖中選擇n-1條邊將所有n個頂點連起來，且n-1條邊的權值之和最小，形象一點說就是找出一條路線遍歷完所有點，不能形成回路且總路程最短，
Kurskal演算法
kurskal演算法的核心思想是將邊按權值排序，每次選出權值最小的邊，只要不會形成回路就加入結果集，如果形成了回路就不選這條邊，類似于貪心的思想，
具體做法是先將邊按權值升序排序然后依次遍歷，判斷是否形成回路的方法是將點劃分不同集合，初始狀態每個點為一個集合，只有當一條邊的兩端分別位于兩個集合時才選擇這條邊，否則就丟棄，這里用到了并查集來處理集合關系，可以參考這篇博文：https://www.cnblogs.com/czc1999/p/11823820.html，選擇一條邊之后要將兩個點合并到同一集合，
模板題： https://www.luogu.com.cn/problem/P3366
代碼如下，還是比較好理解的，時間復雜度為\(O(MlogM)\)，
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int pre[5005];
int Find(int x) { return pre[x] == x ? pre[x] : pre[x] = Find(pre[x]); }
struct line
{
int from, to, val;
bool operator<(line a) { return val < a.val; }
}Arr[200005];
int Kruskal()
{
sort(Arr, Arr + m);
int cnt = n, res = 0;
for (int i = 0; i < m && cnt > 1; i++)
{
int x = Find(Arr[i].from), y = Find(Arr[i].to);
if (x != y)//x和y不在一個集合
{
pre[x] = y;//合并兩個集合
cnt--;//找到了一條邊
res += Arr[i].val;
}
}
return cnt == 1 ? res : -1;//如果cnt不等于1說明沒找到n-1條邊，無最小生成樹
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)pre[i] = i;
for (int i = 0; i < m; i++)cin >> Arr[i].from >> Arr[i].to >> Arr[i].val;
int res = Kruskal();
if (-1 == res)cout << "orz"; else cout << res;
return 0;
}
prim演算法
Kruskal演算法是選擇邊的思路，而prim演算法通過選擇點來得到最小生成樹，有點類似于Dijkstra的感覺，初始源點可以任意選擇，把點劃分成已選擇的點和未選擇的點兩個集合，需要維護一個dis陣列代表每個點到已選擇點的最短距離，不斷把dis最小的未選擇點加入已選擇點集合然后更新dis，當所有點都變成已選擇點(dis==0)的時候就得到了最小生成樹，
代碼如下，真的是跟Dijkstra很像了，
#include <iostream>
#include <algorithm>
using namespace std;
#define inf 2000000000
int n, m;
int dis[5005];
int total = 0;
int head[5005], val[400005], to[400005], nextL[400005];
void AddLine(int a, int b, int c)
{
total++;
to[total] = b;
val[total] = c;
nextL[total] = head[a];
head[a] = total;
}
int Prim()
{
int res = 0;
for (int i = 2; i <= n; i++)dis[i] = inf;
for (int i = 0; i < n; i++)//回圈n次找n個點
{
int Min = inf, u = 1;
for (int j = 1; j <= n; j++)//找下一個最近的未選擇點
{
if (dis[j] != 0 && dis[j] < Min)
{
Min = dis[j]; u = j;
}
}
if (Min == inf && u != 1)return -1;//如果遍歷之后未選擇點dis都為inf，說明該圖是非連通圖
res += dis[u];
dis[u] = 0;
for (int j = head[u]; j; j = nextL[j])//更新該點周圍的dis
{
if (dis[to[j]] > val[j])dis[to[j]] = val[j];
}
}
return res;
}
int main() {
cin >> n >> m;
int a, b, c;
for (int i = 0; i < m; i++)
{
cin >> a >> b >> c;
AddLine(a, b, c);
AddLine(b, a, c);
}
int res = Prim();
if (-1 == res)cout << "orz"; else cout << res;
return 0;
}
堆優化
既然prim也是要每次取dis最小的點，當然也和Dijkstra一樣可以用堆優化，樸素的prim時間復雜度為\(O(n^2)\)，優化后達到\(O(nlogn)\)，代碼如下：
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define inf 2000000000
int n, m;
int dis[5005];
int total = 0;
int head[5005], val[400005], to[400005], nextL[400005];
bool mark[5005];
void AddLine(int a, int b, int c)
{
total++;
to[total] = b;
val[total] = c;
nextL[total] = head[a];
head[a] = total;
}
typedef pair<int, int> p;
priority_queue<p, vector<p>, greater<p>> q;
int Prim()
{
int res = 0;
for (int i = 2; i <= n; i++)dis[i] = inf;
q.push(p(0, 1));
while (!q.empty())
{
int u=q.top().second,v=q.top().first;
q.pop();
if (mark[u])continue;
mark[u] = true;
dis[u] = 0;
res += v;
for (int i = head[u]; i ; i=nextL[i])
{
if (dis[to[i]] > val[i])
{
dis[to[i]] = val[i];
q.push(p(val[i], to[i]));
}
}
}
return res;
}
int main() {
cin >> n >> m;
int a, b, c;
for (int i = 0; i < m; i++)
{
cin >> a >> b >> c;
AddLine(a, b, c);
AddLine(b, a, c);
}
int res = Prim();
if (-1 == res)cout << "orz"; else cout << res;
return 0;
}
所以選擇使用哪個演算法就看是點多還是邊多了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91956.html
標籤：其他
上一篇：快速排序演算法