带权连通图的最小生成树——PRIM普瑞姆算法的理解

1. 图上任意找一点

2. 找到 与 步骤一的点连接的点中权值最小的那个点。

3. 将上述的两个点作为一个整体，找出 与此两个点相连 权值最小的第三个点

4. 将上述3个点 形成的树作为整体 只考虑 度是1的点的连线的最小权值，寻找第四个点。

5. 重复上述步骤 。

6. 所有点找完后就是 最小生成树。

9fb316cd967dc54ff48dd62a2719aeb0.jpg

```
// 代码是优化过的，细节很多 ，所以强行理解 有一定难度
void MiniSpanTree(MGraph G)
{
int min ,i,j,k;
int adjvex[MAXVEX];
int lowcost[MAXVEX];
lowcost[0]=0;
adjvex[0]=0;

for (i=1; i<G.numVertexes;i++)
{

    lowcost[i]= G.arc[0][i];
    adjvex[i] =0;
}

for(i=1 ;i<G.numVertexes;i++)
{
    min = INFININY;
    j=1;
    k=0;
    // 初始化 lowcost 并找出最小的连接点
    while (j<G.numVertexes)
    {
        if(lowcost[j]!=0&& lowcost[j]<min)
        {
             min=lowcost[j];
             k=j;
        }
        j++;

    }
    printf("(%d,%d)",adjvex[k],k);
    //  记录 最小的点
    lowcost[k]=0;

    for (j=1;j<G.numVertexes;j++)
    {
         if(lowcost[j]!=0&& G.arc[k][j]<lowcost[j])
         {
              lowcost[j]=G.arc[k][j];
               adjvex[j]=k;
         }
    }
}

}