发表文章

[最新] 数据结构学习日志之二十二--普里姆算法

chanbendong 1月前 0

假设在n个城市之间建立通信联络网,则联通n个城市最少需要n-1条线路,最多需要n(n-1)/2条线路,连接两个城市必然需要付出一定的代价,假设有一个连通网,代表n个城市和n个城市间可能设置的通信线路,网的顶点代表n个城市,边代表线路,边上的权值代表需要连接这两个城市付出的代价。对于n个顶点的连通网可以建立许多不同的生成树,那么有一棵树必然是耗费最小代价的,那么这棵树就是最小生成树。

生成最小生成树有两种算法,一种是普里姆(prim)算法,一种是克鲁斯卡尔(kruskal)算法

我们来介绍普里姆算法

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


以上图为例: 

1.以a点开始,最小权值为1,另一顶点是c,将c加入到最小生成树中。此时树 a-c

2.在最小生成树的顶点找到一个权值最小且另一顶点不在树中的,最小权值是4,另一顶点是f,将f加入到树里面。此时树为a-c-f

3.重复上一个步骤,a-c-f-d;  a-c-f-d-b;  a-c-f-d-b-e;

实现:

以上图为例,假设初始点为a,把连接A点的线标记为紫线


选择权值最小的线涂成红线,相邻顶点涂黑


接下来,把黑点与蓝点相连的线都涂成紫色,与两个黑点相连的蓝点取权值小的作为紫线


接下来在所有紫线里面选择权值最小的涂红,相邻顶点涂黑


以此类推



首先定义我们的顶点数组:point[6] = {A,B,C,D,E,F},我们用一个辅助数组lowcost[100]用存取这些紫色边,以顶点A为例,lowcost[100] = {0,6,1,5,INF,INF}(INF代表无穷大),值为0的下标表示已经加入生成树,值为INF标识暂无跟该顶点相关联。closet[100]用来存储其他节点到最小生成树中最近的点(实际上是为了打印最小生成树而建立的前驱节点集合),因为初始顶点下标为0,一开始closet[100] = {0,0,0,0,0,0},以此代表第一个图。

我们从lowcost[100]知道,值为1的下标即是我们要加入生成树的顶点,也就是‘C’,所以lowcost数组里面下标为2的值变为0,并且更新了紫线是lowcost[100] = {0,5,0,5,6,4},closet数组也更新为closet[100] = {0,2,0,0,2,2}

接下再次更新,

lowcost[100] = {0,5,0,2,6,0},closet[100] = {0,2,0,5,2,2}

lowcost[100] = {0,5,0,0,6,0},closet[100] = {0,2,0,5,2,2}

lowcost[100] = {0,0,0,0,3,0},closet[100] = {0,2,0,5,1,2}

lowcost[100] = {0,0,0,0,0,0} closet[100] = {0,2,0,5,1,2}

void Prim(MGraph g,int v)
{
    int lowcost[MAXV];          //顶点i是否在U中
    int min;
    int closest[MAXV],i,j,k = 0;
    for (i=0; i<g.n; i++)           //给lowcost[]和closest[]置初值
    {
        lowcost[i]=g.edges[v][i];
        closest[i]=v;
    }
    lowcost[v] = 0;
    for (i=1; i<g.n; i++)           //找出n-1个顶点
    {
        min=INF;
        for (j=0; j<g.n; j++)     //在(V-U)中找出离U最近的顶点k
            if (lowcost[j]!=0 && lowcost[j]<min)
            {
                min=lowcost[j];
                k=j;            //k记录最近顶点的编号
            }
        printf(" 边(%d,%d)权为:%d\n",closest[k],k,min);
        lowcost[k]=0;           //标记k已经加入U
        for (j=0; j<g.n; j++)       //修改数组lowcost和closest
            if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
            {
                lowcost[j]=g.edges[k][j];
                closest[j]=k;
            }
        printf("closet: ");
        for (int i = 0; i < 6; i++) {
            printf("%d ",closest[i]);
        }
    }
    
    
}

相关推荐
最新评论 (0)
返回
发表文章
chanbendong
文章数
27
评论数
0
注册排名
715713