最小生成树——Prim算法

prim算法是生成最小生成树的一个重要方法，它非常类似于最短路径的Dijastra算法. Prim算法的特点是树的集合中的边总是形成单颗树。

Prim算法的主要过程是：

从图中某一顶点u出发，作为树集合U的根节点，然后在集合W=V-U和集合U中寻找两个顶点u∈U,w∈V-U, 使得这两个顶点的边(u,w)是这两个集合顶点连接的边中权值最小的, 然后将顶点w

加入到集合U中，同时记录加入的这个边。重复这个过程只到集合W中所有的顶点w都加入到了U中，或者说W成为空集。

Prim算法的主要步骤如下图演示：

Prim的算法代码如下（这个代码中，寻找最小权值是用的遍历，并没有优化，算法导论里面用的是优先队列）：

#define INF 0x3f3f3f3f

int graph[2001][2001];    //图矩阵
int rec[2001];                    //记录点i是否加入到集合U中
int lowcost[2001];            //记录W集合的点到U中的点形成的边的最小值

int prim(int N)
{
    int minc,i,j,k,mark,total=0;
    memset(rec,0,sizeof(rec));
    memset(lowcost,0,sizeof(lowcost));
    rec[0]=1;      //将根加入集合U
    for(i=0;i<N;i++)
        lowcost[i]=graph[0][i];    //更新最小权值
    for(i=1;i<N;i++)
    {
        minc=INF;
        // 寻找最小权值
        for(j=1;j<N;j++)
        {
            if(rec[j]==0&&lowcost[j]<minc)
            {
                minc=lowcost[j];
                mark=j;
            }
        }
        //将点w加入集合U，并更新两集合间的最新权值
        rec[mark]=1;
        total+=minc;
        for(j=1;j<N;j++)
        {
            if(rec[j]==0&&lowcost[j]>graph[mark][j])
            {
                lowcost[j]=graph[mark][j];
            }
        }
    }
    return total;
}