网站动画特效,手机怎么建设网站,源代码怎么做网站,推广计划和推广单元转自#xff1a;ivy-endhttp://www.ivy-end.com/archives/943背景最小生成树#xff08;Minimum Spanning Trees#xff09;#xff0c;简称MST。是图论中一个非常重要的概念。解决这个问题有两种算法#xff0c;今天暂且先来讨论一下Prim Algorithm。不做特别说明#x… 转自ivy-endhttp://www.ivy-end.com/archives/943背景最小生成树Minimum Spanning Trees简称MST。是图论中一个非常重要的概念。解决这个问题有两种算法今天暂且先来讨论一下Prim Algorithm。不做特别说明讨论的都是无向图。首先介绍一下最小生成树的概念我们知道图可以这样定义 G(V,E) 其中 G 表示图V 表示顶点集合E 表示边集合。最小生成树是这样一棵树它满足通俗地讲就是使得图GG连通时所选取的边的长度的和最小。如上图加粗的路径就是在最小生成树上的路径。算法讲解现在我们开始讨论Prim Algorithm。这个算法可以分为下面几个步骤将顶点集 V 分成两个集合 A 和 B其中集合 A 表示目前已经在MST中的顶点而集合 B 则表示目前不在 MST 中的顶点。寻找与集合 A 连通的最短的边 (u,v)将这条边加入最小生成树中。此时,与(u,v) 相连的顶点不妨设为 Bi也应加入集合 A 中重复第二步直至集合 B 为空集。算法的大体思想就是这样了。为了方便理解我们先来看一下下面一张图片对照上面的图片想必对于Prim Algorithm也有了一定的理解。下面我们来设计算法显然我们需要遍历集合 A 中所有顶点及与之相连的边取连接到集合B的权值最小的边加入最小生成树。这样一来复杂度将达到 O(n3)。我们可以对这个想法进行优化。我们维护一 pCost[i] 数组用来表示从集合A到与之相邻的节点的最小费用。这样我们只要每次取这个数组中的最小值把它在集合B中所对应的结点Vi加入到集合A中。每次加入结束以后都要更新pCost[i]数组。即枚举所有与结点Vi相连的边判断是否比pCost[i]数组中的最小费用小如果比它小则更新。这样可以将算法优化到O(n2)。代码如下#include iostream#include memory.h #include vectorusing namespace std;const int MAX 1024;const int INF 2147483647; // 设置最大权值 int N, M;vectorpairint, int pMap[MAX]; // 邻接表 void Prim();int main(){ cin N M; for(int i 1; i M; i) { int u, v, w; cin u v w; pMap[u].push_back(make_pair(v, w)); pMap[v].push_back(make_pair(u, w)); } Prim(); return 0;}void Prim(){ int nCost 0; vectorint pMST; // 储存MST的结点 int pCost[MAX]; // 储存与集合A相邻的顶点的最小权值0表示该结点已经在MST中 pMST.push_back(1); // 将结点1加入MST pCost[1] 0; for(int i 2; i N; i) // 初始化切记要将除1以外的都置为INF { pCost[i] INF; } for(int i 0; i pMap[1].size(); i) // 处理与结点1相连的顶点 { pCost[pMap[1][i].first] pMap[1][i].second; } for(int i 1; i N - 1; i) // 剩余N-1个顶点循环N-1次 { int nVertex 0, nWeight INF; // 用于寻找最短的边 for(int j 1; j N; j) { if(nWeight pCost[j] pCost[j] ! 0) { nVertex j; nWeight pCost[j]; } } pCost[nVertex] 0; pMST.push_back(nVertex); // 将节点nVertex加入MST nCost nWeight; // 计算MST的费用 for(int j 0; j pMap[nVertex].size(); j) // 更新pCost数组 { if(pCost[pMap[nVertex][j].first] ! 0 pCost[pMap[nVertex][j].first] pMap[nVertex][j].second) { pCost[pMap[nVertex][j].first] pMap[nVertex][j].second; } } } cout MST Cost is nCost endl; cout The vertexs in MST are ; for(int i 0; i pMST.size(); i) { cout pMST[i] ; } cout endl;}
