国外网站建立,wordpress 建多站,以营销网建为,道客网站建设推广小程序Prim算法求最小生成树:
每次将离连通部分的最近的点和点对应的边加入的连通部分#xff0c;连通部分逐渐扩大#xff0c;最后将整个图连通起来#xff0c;并且边长之和最小。
#include iostream
#include cstring
#include algorithm
using names…Prim算法求最小生成树:
每次将离连通部分的最近的点和点对应的边加入的连通部分连通部分逐渐扩大最后将整个图连通起来并且边长之和最小。
#include iostream
#include cstring
#include algorithm
using namespace std;const int N 510;int g[N][N];//存储图
int dist[N];//存储各个节点到生成树的距离
bool st[N];//节点是否被加入到生成树中
int pre[N];//节点的前驱节点用于输出各个边时需要该题不需要
int n, m;//n 个节点m 条边void prim()
{memset(dist,0x3f3f3f3f, sizeof dist);//初始化距离数组为一个很大的数10亿左右int res 0;dist[1] 0;//从 1 号节点开始生成 for(int i 0; i n; i)//每次循环选出一个点加入到生成树{int t -1;for(int j 1; j n; j)//每个节点一次判断直到遍历完全部的点找到未在生成树的点的最小距离点{if(!st[j] (t -1 || dist[j] dist[t]))//如果没有在树中且到树的距离最短则选择该点t j;}//如果孤立点直返输出不能然后退出if(dist[t] 0x3f3f3f3f){printf(impossible\n);return;}st[t] 1;// 选择该点res dist[t];//生成树总长度加该点的长度就是新的总长度for(int i 1; i n; i)//更新生成树外的点到生成树的距离{//从 t 到节点 i 的距离小于原来距离则更新。//因为以前i的距离是到树的某个点的距离现在树加入了t节点所以判断是否i跟t更近是则更新i到树的距离!st是判断是否是树外的点if(dist[i] g[t][i] !st[i]){dist[i] g[t][i];//更新距离pre[i] t;//从 t 到 i 的距离更短i 的前驱变为 t.}}}printf(%d\n,res);return;
}void getPath()//输出各个边,该题不需要
{for(int i n; i 1; i--)//n 个节点所以有 n-1 条边。{printf(%d %d\n,i,pre[i]);// i 是节点编号pre[i] 是 i 节点的前驱节点。他们构成一条边。}
}int main()
{memset(g, 0x3f3f3f3f, sizeof(g));//各个点之间的距离初始化成很大的数scanf(%d%d,n,m);//输入节点数和边数while(m --){int a, b, w;scanf(%d%d%d,a,b,w);//输入边的两个顶点和权重g[a][b] g[b][a] min(g[a][b],w);//存储权重因为是无向图所以ab和ba都要赋值}prim();//求最小生成树return 0;
}
