最小生成树

定义

最小生成树(MST)是一个连通加权无向图中一棵权值最小的生成树。

主要操作

作为一个图论模型,应用在很多方面。

时间及空间复杂度

时间复杂度

kruskal算法为$O(E\log E)$

prim算法为$O(E+V\log V)$

空间复杂度

为图的空间消耗加上并查集的空间消耗

模板

 1 const int MAXN = 666666;
 2 int fa[MAXN];
 3 int get(int x){return x == fa[x] ? x : fa[x] = get(fa[x]);}
 4 void merge(int x,int y){fa[get(x)] = get(y);}
 5 struct Edge{
 6     int u,v,d;
 7     Edge(int u,int v,int d){this -> u = u;this -> v = v;this -> d = d;}
 8     bool operator < (const Edge &rhs) const {return d < rhs.d;}
 9 };
10 class Kruskal{
11 public:
12     int n,m;
13     std::vector<Edge> E;
14     Kruskal(int n,int m){this -> n = n;this -> m = m;for(int i = 1;i <= n;i++) fa[i] = i;}
15     void addEdge(int u,int v,int d){E.push_back(Edge(u, v, d));}
16     int kruskal(){
17         int ans = 0;
18         std::sort(E.begin(),E.end());
19         for(int i = 0;i < m;i++){
20             int u = get(E[i].u);int v = get(E[i].v);
21             if(u == v) continue;
22             merge(u, v);
23             ans += E[i].d;
24         }
25         return ans;
26     }
27 };