1. Kruskal(并查集模板)：

/*Kruskal：并查集實現，記錄兩點和距離，按距離升序排序，O (ElogE) */ struct Edge {int u, v, w;bool operator < (const Edge &r) const {return w < r.w;} }edge[E]; sort (edge+1, edge+1+m); if (!uf.same (x, y)) uf.Union (x, y), ans += w;

?

?

2. Prim：

O (n ^ 2)：

/*Prim：Dijkstra思想，鄰接矩陣實現，適合稠密圖, O (n ^ 2)不連通返回-1，或返回最小生成樹長度(MST) */ int Prim(int s) {memset (vis, false, sizeof (vis));memset (d, INF, sizeof (d)); d[s] = 0;int ret = 0;for (int i=1; i<=n; ++i) {int mn = INF, u = -1;for (int i=1; i<=n; ++i) {if (!vis[i] && d[i] < mn) mn = d[u=i];}if (u == -1) return -1;vis[u] = true; ret += d[u];for (int i=1; i<=n; ++i) {if (!vis[i] && d[i] > w[u][i]) {d[i] = w[u][i];}}}return ret; }

?

O (ElogV)：

/*Prim：Dijkstra思想，優先隊列優化，適合稀疏圖，O (ElogV)不連通返回-1，或返回最小生成樹長度(MST) */ int Prim(int s) {memset (vis, false, sizeof (vis));memset (d, INF, sizeof (d));priority_queue<Edge> Q;for (int i=head[s]; ~i; i=edge[i].nex) {int v = edge[i].v, w = edge[i].w;if (d[v] > w) {d[v] = w; Q.push (Edge (v, d[v]));}}vis[s] = true; d[s] = 0; int ret = 0;while (!Q.empty ()) {int u = Q.top ().v; Q.pop ();if (vis[u]) continue;vis[u] = true; ret += d[u];for (int i=head[u]; ~i; i=edge[i].nex) {int v = edge[i].v, w = edge[i].w;if (!vis[v] && d[v] > w) {d[v] = w; Q.push (Edge (v, d[v]));}}}return ret; }

　　

轉載于:https://www.cnblogs.com/Running-Time/p/4781736.html

總結

以上是生活随笔為你收集整理的Kruskal Prim模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。