[算法与数据结构] - No.9 图论（2）- 最小生成树Prim算法与Kruskal算法

普里姆算法的基本思想：
    从连通网络 N = { V, E }中的某一顶点 u0 出发, 选择与它关联的具有最小权值的边 ( u0, v ), 将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在 U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合 U 中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。

如图所示：

算法实现：

设初始总的顶点集合为V，已加入最小生成树的集合点为S

定义两个辅助数组：lowcost[] 和 nextvex[],分别用来记录下标为i的到S中点最近的距离。每一次选取不在S中，同时距离S最近的点vi。将vi加入S中，同时在lowcost

中更新所有不在S中的, 与vi相连的点vj到S的最近距离。更新nextvex中vj下标的值为vi,即nextvex[vj] = vi

#include <iostream>
#include <stdlib.h>
using namespace std;
const int MAX =99999999;
int main()
{
    unsigned int n,e;
    cin>>n>>e;
    if(n>0&&e>0)
    {
        int arr[100][100];
        int nextvex[100] = {0};
        nextvex[0] = -1;
        int lowcost[100] = {0};
        for(int i=0; i<100; i++)
        {
            for(int j=0; j<100; j++)
            {
                if(i!=j)
                    arr[i][j] = MAX;
                else
                    arr[i][j] = 0;
            }
        }
        for(int i=0; i<e; i++)
        {
            int from,to,dis;
            cin>>from>>to>>dis;
            arr[from][to] = dis;
            arr[to][from] = dis;
            //arr[to][from] = dis;
        }
        for(int j =0;j<n;j++)
        {
            lowcost[j] = arr[0][j];
        }

        /*for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                cout<<arr[i][j]<<" ";
            }
            cout<<endl<<endl;
        }*/
        int cnt = 1;
        while(cnt<n)
        {
            int temp = MAX;
            int vertex;
            for(int k = 0;k<n;k++)
            {
                if(nextvex[k]!=-1&&lowcost[k]<temp)
                {
                    temp = lowcost[k];
                    vertex = k;
                }
            }
            cout<<nextvex[vertex]<<"->"<<vertex<<":"<<temp<<endl;
            nextvex[vertex] = -1;
            for(int l = 0;l<n;l++)
            {
                if(arr[vertex][l]<MAX&&nextvex[l]!=-1)
                {
                    lowcost[l] = arr[vertex][l];
                    nextvex[l] = vertex;
                }
            }
            cnt = cnt + 1;

        }
    }
    return 0;
/*
7 9
0 1 28
0 5 10
1 2 16
1 6 14
2 3 12
3 4 22
3 6 18
4 5 25
4 6 24

*/
}

Kruskal算法基本思想：

j将所有的边排序。将所有的边加入集合S，即一开始S = E  。从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E'  。重复直到所有点属于同一棵树，边集E'就是一棵最小生成树

这个算法的思想很简单，但是其中有个地方值得注意。那就是如何判断两个点是否处于同一个连通分量（同一棵树里），这里用到了并查集：

并查集：当我们需要判断某两个元素是否属于统一集合（这里是树），在数据量比较大的时候，我们用到了并查集。并查集中有两个重要的函数（初始化函数除外），按秩合并和路径压缩

初始化：

typedef struct Edge{
    int from;
    int to;
    int cost;
}Edge;
Edge edgeList[100];

int nodeRank[100];
int nodeFather[100];
void Init(int n)
{
    for(int i = 0 ;i<n;i++)
    {
        nodeRank[i] = 0;
        nodeFather[i] = i;
    }
}

首先，我们定义一个边的结构体。这个结构体里面定义了每个边的两个端点。同时记录这条边的长度。在初始化的函数中，我们设置每个节点的父节点是自身，同时每个节点的秩都是0。

路径压缩：

int findFather(int x)
{
    int root = x;
    while(nodeFather[root]!=root)
    {
        root = nodeFather[root];
    }
    while(x!=root)
    {
        int father = nodeFather[x];
        nodeFather[x] = root;
        x = father;
    }
    return root;
}

在我们查找两个节点是否处于同一个树的时候，我们的方法是不断找当前节点的父节点，查看其父节点是否为自身。如果是，该节点为该树的根；否则迭代该过程。但是，随着树的增加，每次查找父节点会很消耗时间。所以我们每次查找父节点的时候，都将除根节点以外所有节点的父节点设为根节点，方便下次查找。

按秩合并：

int unite(int x,int y)
{
    int fatherx = findFather(x);
    int fathery = findFather(y);
    if(nodeRank[fatherx]>nodeRank[fathery])
    {
        nodeFather[fathery] = fatherx;
    }
    else
    {
        nodeFather[fatherx] = fathery;
        if(nodeRank[fatherx] == nodeRank[fathery])
        {
            nodeRank[fathery]++;
        }
    }
}

如果两个子节点不在同一树里边，那么我们设置秩（我们这里是根节点的索引大小）较小的根指向秩比较大的根。

当最小生成树中的边的个数达到n-1的时候，算法结束

完整代码如下：

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct Edge{
    int from;
    int to;
    int cost;
}Edge;
Edge edgeList[100];
int cmp(const void*first,const void*second)
{
    return ((Edge*)first)->cost - ((Edge*)second)->cost;
}
int nodeRank[100];
int nodeFather[100];
void Init(int n)
{
    for(int i = 0 ;i<n;i++)
    {
        nodeRank[i] = 0;
        nodeFather[i] = i;
    }
}
int findFather(int x)
{
    int root = x;
    while(nodeFather[root]!=root)
    {
        root = nodeFather[root];
    }
    while(x!=root)
    {
        int father = nodeFather[x];
        nodeFather[x] = root;
        x = father;
    }
    return root;
}

int unite(int x,int y)
{
    int fatherx = findFather(x);
    int fathery = findFather(y);
    if(nodeRank[fatherx]>nodeRank[fathery])
    {
        nodeFather[fathery] = fatherx;
    }
    else
    {
        nodeFather[fatherx] = fathery;
        if(nodeRank[fatherx] == nodeRank[fathery])
        {
            nodeRank[fathery]++;
        }
    }
}

void Kruskal(int n,int e)
{
    int cnt = 0;
    qsort(edgeList,e,sizeof(Edge),cmp);
    /*for(int i = 0 ; i <e;i++)
    {
        cout<<edgeList[i].from<<" "<<edgeList[i].to<<" "<<edgeList[i].cost<<endl;
    }*/
    for(int i = 0 ; i<e&&cnt!=n-1;i++)
    {
        if(findFather(edgeList[i].from)!=findFather(edgeList[i].to))
        {
            cout<<edgeList[i].from<<" "<<edgeList[i].to<<endl;
            unite(edgeList[i].from,edgeList[i].to);
            cnt++;
        }
    }
}
/*
//一种优美的递归形式
int unionsearch(int x)
{
   if(x!=father[x])
   {
        father[x] = find(father[x]);
   }
   return father[x];
}
*/
int main()
{
    cout<<"请输入顶点数和边数："<<endl;
    int n,e;
    cin>>n>>e;

    for(int i = 0 ; i <e;i++)
    {
        cin>>edgeList[i].from>>edgeList[i].to>>edgeList[i].cost;
    }
    Init(n);
    Kruskal(n,e);

    return 0;

/*
7 9
0 1 28
0 5 10
1 2 16
1 6 14
2 3 12
3 4 22
3 6 18
4 5 25
4 6 24

*/
}

P.S. 文章不妥之处还望指正