14、最小生成树算法之Prim算法(C++实现)
在无向带权连通图G中,如果一个连通子树包含所有顶点,并且连接这些顶点的边权之和最小,那么这个连通子图就是G的最小生成树。求最小生成树的一个常见算法是Prim算法,该算法的基本思想是:
1)设置两个集合V和S,任意选择一个顶点作为起始顶点,将起始顶点放入集合S,其余顶点存入集合V中;
2)然后使用贪心策略,选择一条长度最短并且端点分别在S和V中边(即为最小生成树的中的一条边),将这条边在V中的端点加入到集合S中;
3)循环执行第2)步直到S中包含了所有顶点。
根据以上思想我们很快可以给出一个O(N^3)的算法,即选择一条最短边需要O(N^2)的时间复杂度,具体实现代码如下:
////////////////////////////////
// O(N^3)
#include
using namespace std;
//用邻接矩阵表示无向图
#define N 6 //节点个数
#define M 100000//最大值,表示不可达
int matrix[N][N]=
{
M,6,1,5,M,M,
6,M,5,M,3,M,
1,5,M,5,6,4,
5,M,5,M,M,2,
M,3,6,M,M,6,
M,M,4,2,6,M
};
void prim()
{
bool flag[N]; //标记某个点是否当前生成树集合中
int i,j;
//初始化集合
for(i = 0; i flag[i] =false; flag[0] = true; int count = 1; while(count++< N) { int min =M; int e1 = -1,e2 = -1; for(i = 0; i< N; ++i) { if(flag[i]) { for(j= 0; j < N; ++j) { if(!flag[j]) { if(matrix[i][j] < min) { min = matrix[i][j]; e1 = i; e2 = j; } } } } } cout< flag[e2] =true; } } int main(int argc, char* *argv) { prim(); system("pause"); return 0; }
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。