Prims算法 - 最小生成树

2017-07-26 14:35:49

Prims算法，是一种基于“贪心”的求最小树的算法，以每次加入一个邻接边来建立最小树，直到找到N-1个边为止。

规则：以开始时生成树的集合为起始的顶点，然后找出与生成树集合邻接的边中，加权值最小的边来生成树，

为了确定新加入的边不会造成回路，所以每一个新加入的边，只允许有一个顶点在生成树的集合中。

适用：稠密图

用自己的话来讲：Prims算法跟之前的Kruskal算法不大一样，Kruskal算法主要是通过对权值进行从低到高的排序，确定先后加入的边

Prims算法则比较高级，从某一个点出发，寻找到跟这个点最近的这个点，两个组成集合，查找离这两个点最近的几个点，找到最近的点，

将其加入到生成树中，组成集合，一直到找到N-1个边为止；

代码如下：

//这里使用无向图

#include <iostream>

using namespace std;

const int MAXN = ;

const int INF = ;

int n,e;

int w[MAXN][MAXN];

int mincount[MAXN]; //从初始顶点到该顶点的最小权值

void init()

{

    int i,j;

    int tx,ty;

    for(i = ; i<=MAXN; i++)

        for(j =; j<MAXN; j++)

            w[i][j] = INF;

    cin >> n >> e;

    for(i = ; i<=e; i++)

    {

        cin >> tx >> ty >> w[tx][ty];

        w[tx][ty] = w[ty][tx];

    }

}

void prim(int s)   //从标号为s处开始生成树

{

    int i,j,cnt = ,min; // cnt 是生成树所有边的权值之和

    int k;

    for(i = ; i<= n; i++)

        mincount[i] = w[s][i]; //  初始化，设w[1][i]是初始点k到i的最小权值，如果没有就设为INF

    mincount[s] = ;

    for(i = ; i < n; i++) //一共有n-1次

    {

        min = INF;

        for(j = ; j <= n; j++)

        {

            if(mincount[j]!= && mincount[j]<min)

            {

                min = mincount[j];

                k = j;        //记录该点

            }

            mincount[k] = ;//将该点加入到最小生成树中

            cnt += min;   //将这条边权值加入到最小生成树中

            for(j = ;j<=n;j++)  //修正初始点到每个点的最小权值

            {

                  if(w[k][j]<mincount[j])

                        mincount[j] = w[k][j];

            }

        }

    }

    cout << cnt << endl;

}

int main()

{

    init();

    prim();

    return ;

}

巴特西

Prims算法 - 最小生成树

最新文章

热门文章