最小生成树的两种方法（Kruskal算法和Prim算法）

关于图的几个概念定义：

• 连通图：在无向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该无向图为连通图。
• 强连通图：在有向图中，若任意两个顶点vivi与vjvj都有路径相通，则称该有向图为强连通图。
• 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
• 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
• 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

下面介绍两种求最小生成树算法

1.kruskal算法

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

2. prim算法

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

1. 图的所有顶点集合为vv；初始令集合u={s},v=v−uu={s},v=v−u;
2. 在两个集合u,vu,v能够组成的边中，选择一条代价最小的边(u0,v0)(u0,v0)，加入到最小生成树中，并把v0v0并入到集合u中。
3. 重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。

由于不断向集合u中加点，所以最小代价边必须同步更新；需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息，：

struct
{
  char vertexdata   //表示u中顶点信息
  uint lowestcost   //最小代价
}closedge[vexcounts]

3. 完整代码

/************************************************************************
csdn 勿在浮沙筑高台 http://blog.csdn.net/luoshixian099算法导论--最小生成树（prim、kruskal）2016年7月14日
************************************************************************/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define infinite 0xffffffff   
#define vertexdata unsigned int  //顶点数据
#define uint  unsigned int
#define vexcounts 6  //顶点数量
char vextex[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
struct node 
{
    vertexdata data;
    unsigned int lowestcost;
}closedge[vexcounts]; //prim算法中的辅助信息
typedef struct 
{
    vertexdata u;
    vertexdata v;
    unsigned int cost;  //边的代价
}arc;  //原始图的边信息
void adjmatrix(unsigned int adjmat[][vexcounts])  //邻接矩阵表示法
{
    for (int i = 0; i < vexcounts; i++)   //初始化邻接矩阵
        for (int j = 0; j < vexcounts; j++)
        {
            adjmat[i][j] = infinite;
        }
    adjmat[0][1] = 6; adjmat[0][2] = 1; adjmat[0][3] = 5;
    adjmat[1][0] = 6; adjmat[1][2] = 5; adjmat[1][4] = 3;
    adjmat[2][0] = 1; adjmat[2][1] = 5; adjmat[2][3] = 5; adjmat[2][4] = 6; adjmat[2][5] = 4;
    adjmat[3][0] = 5; adjmat[3][2] = 5; adjmat[3][5] = 2;
    adjmat[4][1] = 3; adjmat[4][2] = 6; adjmat[4][5] = 6;
    adjmat[5][2] = 4; adjmat[5][3] = 2; adjmat[5][4] = 6;
}
int minmum(struct node * closedge)  //返回最小代价边
{
    unsigned int min = infinite;
    int index = -1;
    for (int i = 0; i < vexcounts;i++)
    {
        if (closedge[i].lowestcost < min && closedge[i].lowestcost !=0)
        {
            min = closedge[i].lowestcost;
            index = i;
        }
    }
    return index;
}
void minispantree_prim(unsigned int adjmat[][vexcounts], vertexdata s)
{
    for (int i = 0; i < vexcounts;i++)
    {
        closedge[i].lowestcost = infinite;
    }      
    closedge[s].data = s;      //从顶点s开始
    closedge[s].lowestcost = 0;
    for (int i = 0; i < vexcounts;i++)  //初始化辅助数组
    {
        if (i != s)
        {
            closedge[i].data = s;
            closedge[i].lowestcost = adjmat[s][i];
        }
    }
    for (int e = 1; e <= vexcounts -1; e++)  //n-1条边时退出
    {
        int k = minmum(closedge);  //选择最小代价边
        cout << vextex[closedge[k].data] << "--" << vextex[k] << endl;//加入到最小生成树
        closedge[k].lowestcost = 0; //代价置为0
        for (int i = 0; i < vexcounts;i++)  //更新v中顶点最小代价边信息
        {
            if ( adjmat[k][i] < closedge[i].lowestcost)
            {
                closedge[i].data = k;
                closedge[i].lowestcost = adjmat[k][i];
            }
        }
    }
}
void readarc(unsigned int  adjmat[][vexcounts],vector<arc> &vertexarc) //保存图的边代价信息
{
    arc * temp = null;
    for (unsigned int i = 0; i < vexcounts;i++)
    {
        for (unsigned int j = 0; j < i; j++)
        {
            if (adjmat[i][j]!=infinite)
            {
                temp = new arc;
                temp->u = i;
                temp->v = j;
                temp->cost = adjmat[i][j];
                vertexarc.push_back(*temp);
            }
        }
    }
}
bool compare(arc  a, arc  b)
{
    return a.cost < b.cost ? true : false;
}
bool findtree(vertexdata u, vertexdata v,vector<vector<vertexdata> > &tree)
{
    unsigned int index_u = infinite;
    unsigned int index_v = infinite;
    for (unsigned int i = 0; i < tree.size();i++)  //检查u,v分别属于哪颗树
    {
        if (find(tree[i].begin(), tree[i].end(), u) != tree[i].end())
            index_u = i;
        if (find(tree[i].begin(), tree[i].end(), v) != tree[i].end())
            index_v = i;
    }
 
    if (index_u != index_v)   //u,v不在一颗树上，合并两颗树
    {
        for (unsigned int i = 0; i < tree[index_v].size();i++)
        {
            tree[index_u].push_back(tree[index_v][i]);
        }
        tree[index_v].clear();
        return true;
    }
    return false;
}
void minispantree_kruskal(unsigned int adjmat[][vexcounts])
{
    vector<arc> vertexarc;
    readarc(adjmat, vertexarc);//读取边信息
    sort(vertexarc.begin(), vertexarc.end(), compare);//边按从小到大排序
    vector<vector<vertexdata> > tree(vexcounts); //6棵独立树
    for (unsigned int i = 0; i < vexcounts; i++)
    {
        tree[i].push_back(i);  //初始化6棵独立树的信息
    }
    for (unsigned int i = 0; i < vertexarc.size(); i++)//依次从小到大取最小代价边
    {
        vertexdata u = vertexarc[i].u;  
        vertexdata v = vertexarc[i].v;
        if (findtree(u, v, tree))//检查此边的两个顶点是否在一颗树内
        {
            cout << vextex[u] << "---" << vextex[v] << endl;//把此边加入到最小生成树中
        }   
    }
}
 
int main()
{
    unsigned int  adjmat[vexcounts][vexcounts] = { 0 };
    adjmatrix(adjmat);   //邻接矩阵
    cout << "prim :" << endl;
    minispantree_prim(adjmat,0); //prim算法，从顶点0开始.
    cout << "-------------" << endl << "kruskal:" << endl;
    minispantree_kruskal(adjmat);//kruskal算法
    return 0;
}