赣州网站建设服务,东营住房和城乡建设部网站,广州分公司注册,规划和设计一个网站最小生成树概念
参考#xff1a;什么是最小生成树#xff1f;
Minimum Spanning Tree
何为生成树#xff1f; 生成树是指一个联通图的极小的连通子图#xff0c;它包含了图中的所有n个顶点#xff0c;并只有n-1条边#xff08;构成一棵树#xff09; 生成树的一些性…最小生成树概念
参考什么是最小生成树
Minimum Spanning Tree
何为生成树 生成树是指一个联通图的极小的连通子图它包含了图中的所有n个顶点并只有n-1条边构成一棵树 生成树的一些性质 一个连通图可以有多种生成树如上图所示生成树中不存在环任何一个边的加入都会使得生成树中出现环
何为最小生成树 最小生成树是针对一个带权图来说的就是指原图中能构成的所有生成树中边权和最小的一颗生成树 对于下面的连通图 可以有多种选取边即构成了生成树的情况 我们称权值和最小的树为最小生成树
最小生成树有什么意义呢 接上图如果我们需要在某城市之间修建道路点与点之间的加权边就是两城市道路的维修费如果我们想找到一种将所有城市都连通起来并且使得道路修建费用最小的一种方案那么就要选择使用最小生成树。 最小生成树构建方法
两种方法都是基于贪心 有一点其实我不太明白。“Kruskal算法维护的是边所以不需要对于无向图存储两次边。Prim维护的是集合之间点的关系因此需要对无向图存储两次边
克鲁斯卡尔算法Kruskal
算法思想 将所有的带权边按照权值从小到大排列从最小的开始选择如果加入该边后不会产生环则加入反之则不加入。直到已经选择了n-1条边。 这里不会产生环的判定比较困难因此可以换一下想法 就是只要选择的边的两端点不在同一连通块中即可。如下所示 使用并查集就可以检查联通问题了 #includeiostream
#includealgorithmusing namespace std;const int N2*1e510;int n,m;
int p[N];
int ans0;//最终权值
int res0;//已经放入的边数struct nn{int a;int b;int w;
}node[N];int cmp(nn a, nn b){return a.wb.w;
}int find(int x){if(p[x]!x) p[x]find(p[x]);return p[x];
}int kruskal(){for(int i1;in;i)p[i]i;for(int i1;im;i){//遍历m条边int anode[i].a, bnode[i].b, wnode[i].w;afind(a); bfind(b);if(a!b){//如果不在一个联通图中p[a]b;//连接两个点answ;res;}if(resn-1){return res;}}return res;
}int main(){cinnm;for(int i1;im;i){cinnode[i].anode[i].bnode[i].w;}sort(node1,node1m,cmp);if(kruskal()n-1)coutansendl;elsecoutimpossibleendl;return 0;
}普里姆算法Prim
和kruskal算法遍历边不同的是prim算法是对点进行遍历
算法思路 对于每个点每次找到一个集合外的距离该集合最近的点t。该集合是一个已经确定了的连通块 用点t更新集合外点到集合的距离就是找集合外和t有连接的点如果更小就更新最后将点t放入集合中。这里描述的不是很清楚 st[j]0(t-1||dist[t]dist[j]) 注意这里的判断首先判断该点是否已经进入集合然后再与上t-1和大小的或运算 #includeiostream
#includealgorithm
#includecstringusing namespace std;const int N510,INF0x3f3f3f3f;
int n,m;int g[N][N];//用于存储边
int dist[N];//点距离集合的距离
int st[N];//表示是否已经进入集合
int ans0;int prim(){dist[1]0;//强制一开始选择的点就是点1for(int i1;in;i){//外层循环是指循环n次以遍历所有n个点int t-1;for(int j1;jn;j){if(st[j]0(t-1||dist[t]dist[j])){tj;} }//找到最短的dist下标为tif(dist[t]INF) return INF;//说明没有点能够到达当前的集合ansdist[t];for(int j1;jn;j){if(st[j]0j!t){//更新所有集合外的点到该集合的距离dist[j]min(dist[j],g[t][j]);}}st[t]1;//将点加入集合}}int main(){cinnm;memset(g,0x3f,sizeof g);for(int i1;im;i){int a,b,c;cinabc;g[a][b]g[b][a]min(g[a][b],c);}memset(dist,0x3f,sizeof dist);if(prim()INF)coutimpossibleendl;elsecoutansendl;return 0;
}
