干货｜最小生成树-prime算法
最小生成树-prime算法～
Prime算法的核心步骤是：在带权连通图中V是包含所有顶点的集合， U已经在最小生成树中的节点，从图中任意某一顶点v开始，此时集合U={v}，重复执行下述操作：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边，将(u,w)这条边加入到已找到边的集合，并且将点w加入到集合U中，当U=V时，就找到了这颗最小生成树。
其实，算法的核心步骤就是：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边。
知道了普利姆算法的核心步骤，下面我就用图示法来演示一下工作流程，如图：
首先，确定起始顶点。我以顶点A作为起始点。根据查找法则，与点A相邻的点有点B和点H，比较AB与AH，我们选择点B，如下图。并将点B加入到U中。
继续下一步，此时集合U中有{A,B}两个点，再分别以这两点为起始点，根据查找法则，找到边BC（当有多条边权值相等时，可选任意一条），如下图。并将点C加入到U中。
继续，此时集合U中有{A,B,C}三个点，根据查找法则，我们找到了符合要求的边CI，如下图。并将点I加入到U中。
继续，此时集合U中有{A,B,C,I}四个点，根绝查找法则，找到符合要求的边CF，如下图。并将点F加入到集合U中。
继续，依照查找法则我们找到边FG,如下图。并将点G加入到U中。
继续，依照查找法则我们找到边FG,如下图。并将点G加入到U中。
继续，依照查找法则我们找到边CD,如下图。并将点D加入到U中。
继续，依照查找法则我们找到边DE,如下图。并将点E加入到U中。
此时，满足U = V，即找到了这颗最小生成树。
同样， 我继续用POJ 2395这题为例子给出代码：
using namespace std;const int MAXN = 2010;const int INF = 1 << 30;int map[MAXN][MAXN];int N, M;int lowcost[MAXN];void init(){for(size_t i = 0; i <= N; ++i)for(size_t j = 0; j <= N; ++j)map[i][j] = INF;}int prime(){for(size_t i = 1; i <= N; ++i)lowcost[i] = map[1][i];int min;bool visited[N + 1];// index begin from 1 not 0int ans = -1;memset(visited, false, sizeof(visited));lowcost[1] = 0;visited[1] = true;for(size_t i = 1; i < N; ++i)//loop N - 1 times{min = INF;int k;for(size_t j = 1; j <= N; ++j)// find the minimun edge between two edge set{if(!visited[j] && min > lowcost[j]){min = lowcost[j];k = j;}}visited[k] = true;ans = ans > min ? ans : min;for(size_t j = 1; j <= N; ++j)// update the array of lowcost{if(!visited[j] && lowcost[j] > map[k][j])lowcost[j] = map[k][j];}}return ans;}int main(){while(cin >> N >> M){init();int x, y, c;for(size_t i = 0; i < M; ++i){cin >> x >> y >> c;if(map[x][y] > c)map[x][y] = c;if(map[y][x] > c)map[y][x] = c;}cout << prime() << endl;}}
更多有趣的内容
请长按
❤
长按二维码关注