最小生成树——普里姆算法

当我们要求解n个连接城市之间的路线问题，就需要我们进行一个计算。

而在连通网上面，我们称这类问题为最小代价生成树（最小生成树）问题。今天我们主要讨论的是用普里姆算法实现最小生成树。

如图所示，a图是一个有权值的连通图。要对其进行最小生成树求解，假设初始点为V1，寻找与1有关系而且权值最小的顶点

                                                                  （图源严蔚敏版数据结构）           V2进行访问，再从点V2寻找下一个有关系而且权值最小的顶点，若访问的点将构成闭合回路，将进行回溯，回溯到上一个点，再进行访问。直至走完所以顶点。

代码实现：

/**求顶点位置**/
int Locatvex(ArrayGraph G,char u)
{
    int i,a;
    for(i=0;i<MAXN;i++)
    {
        if(u==G.vex[i])///循环求得u顶点的位置
        {
            a=i;
            return a;///返回a
        }
    }
    a=-1;
    return a;
}
/**返回最小代价边**/
int minimum(struct node *closedage)
{
    int MIN=INF;///MIN用于表示最短距离
    int k=-1;
    int i;
    for(i=0;i<MAXN;i++)
    {
        if(closedage[i].lowcost<MIN&&closedage[i].lowcost!=0)///如果两顶点有关系，且权值小于MIN
        {
            MIN=closedage[i].lowcost;///更新MIN，直至找到最近的顶点
            k=i;
        }
    }
    return k;
}
/**最小生成树**/
void primG(ArrayGraph G,char u)///u表示规定的起始点
{
    int i,j;
    int k;
    k=Locatvex(G,u);///求取顶点位置
    for(i=0;i<MAXN;++i)
    {
        if(i!=k)
        {
            closedage[i].data=u;
            closedage[i].lowcost=G.arcs[k][i];
        }
    }
    closedage[u].lowcost=0;///初始化

    for(i=0;i<MAXN;i++)///循环寻找下一个顶点
    {
        k=minimum(closedage);///k为两顶点最小权值
        printf("%c\t",G.vex[k]);///输出
        closedage[k].lowcost=0;
        for(j=0;j<MAXN;j++)
        {
            if(G.arcs[k][j]<closedage[j].lowcost)
            {
                closedage[j].data=G.vex[k];
                closedage[j].lowcost=G.arcs[k][j];
            }
        }
    }
}

运行结果：

时间复杂度：O（n²）

假设图中共有n个顶点，则进行第一个循环的频度为n，第二个循环的频度为n-1。而重新求取最小代价边的频度为n。因此时间复杂度为O（n²）