最小生成树 Kruskal&&Prim

2019-11-14 09:26:00

字体：大中小

来源：转载

供稿：网友

Kruskal 算法先将途中所有边的权值进行从小到大排序，按照顺序依次将边的两点加入最小生成树的子图中，若加入后产生圈，则舍弃这条边，直到所有点在图中为止

1).记Graph中有v个顶点，e个边2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边3).将原图Graph中所有e个边按权值从小到大排序4).循环：从权值最小的边开始遍历每条边直至图Graph中所有的节点都在同一个连通分量中如果这条边连接的两个节点于图Graphnew中不在同一个连通分量中就添加这条边到图Graphnew中#include<iostream>#include<vector>#include<algorithm>#include<cstdlib>#include<cmath>#include<stack>#include<queue>#include<cstdio>#include<string>#include<cstring>#include<map>#include<set>using namespace std;#define N 100#define INF 0x3f3f3f3f/*****************************************************/struct node{ int u, v, cost;};bool cmp(node a, node b){ return a.cost < b.cost;}node s[N];int par[N];int ranks[N];int V, E;void init_union_find(int v);int find(int x);void unite(int a, int b);bool same(int a, int b);int Kruskal();int main(){ cin >> V >> E; //输入点、边数 init_union_find(V); //初始化并查集 for (int i = 0; i < E; i++){ cin >> s[i].u >> s[i].v >> s[i].cost; } cout<<Kruskal();}int Kruskal(){ sort(s, s + E, cmp); //对边的权值进行排序 int res = 0; for (int i = 0; i < E; i++){ node e = s[i]; if (!same(e.u, e.v)){ //判断两点是否在一个通路 unite(e.u, e.v); //合并两个点 res += e.cost; } } return res;}void init_union_find(int v){ for (int i = 0; i <= V; i++) { par[i] = i; ranks[i] = 1; }}void unite(int a, int b){ a = find(a); b = find(b); if (a==b)return; if (ranks[a] < ranks[b]){ par[a] = b; } else{ if (ranks[a] == ranks[b]) { ranks[a]++; } par[b] = a; }}int find(int x){ if (par[x] == x)return x; return par[x] = find(par[x]);}bool same(int a, int b){ if (par[a] == par[b])return true; return false;}

PRim算法先建立一个最小生成树的子图。任取一点s最为子图的初始点，标记。然后再子图之外寻找与子图中所有点距离最小的点，将这个点加入子图的集合，并从这个点进行扩展求出相邻点到子图的最短距离

#define N 500+10#define INF 0x3f3f3f3f#define mem(arr,num) memset(arr,num,sizeof(arr))/**********************************************************/int minCost[N]; //某一点到子图的最短距离int cost[N][N]; int V, E;bool used[N];int Prim(){ mem(used, 0); mem(minCost, 0x3f); int res = 0; minCost[1] = 0; while (1){ int v = -1; for (int i = 1; i <= V; i++){ if (!used[i] && (v == -1 || minCost[i] < minCost[v])) v = i; //找到到子图权值最小的点 } if (v == -1)break; used[v] = true; res += minCost[v]; for (int i = 1; i <= V; i++){ minCost[i] = min(minCost[i], cost[v][i]); //求出该点周围的点距离子图权值的最小值 } } return res;}

上一篇：Java 程序员不容错过的开发趋势

下一篇：BZOJ 1050 旅行comf【暴力枚举+生成树】