最小生成樹的prim算法：pku2485Highways、PKU1258Agri-Net解題報告

對于圖，其生成樹中的邊也帶權，将生成樹各邊的權值總和稱為生成樹的權，并将權值最小的生成樹稱為最小生成樹（Minimun Spanning Tree），簡稱為MST。有兩種非常典型的算法：Prim算法和kruskal算法，這兩種算法都采用了貪心政策。 Prim算法的基本思想是：

(1) 在圖G=(V,E)（V表示頂點，E表示邊）中，從集合V中任取一個頂點（例如取頂點v0）放入集合U中，這時U={v0}，集合T(E)為空。

(2) 從v0出發尋找與U中頂點相鄰（另一頂點在V中）權值最小的邊的另一頂點v1，并使v1加入U。即U={v0,v1}，同時将該邊加入集合T(E)中。

(3) 重複(2)，直到U = V為止。

這時T(E)中有n-1條邊，T=(U,T(E))就是一棵最小生成樹。 在本例中，數組origin存放原始資料，max_distance存放矩陣中的最大值， result 存放最小生成樹的最大邊，opt存放節點和最小生成樹之間的最小距 離, flag判斷是否已經加入到最小生成樹中，首先将1号頂點加入最小生成樹 中，flag[1]為true，其他為false，opt[i]的值為origin[1][i]的值，然後選 擇不在最小生成樹中的最小邊i，然後加入到最小生成樹中，另外更新

opt[i],flag[i]。如此反複，直到取到v-1條邊為止。

AC代碼：

//采用prim算法求最小生成樹

#include <stdio.h>

int main(void)

{

    //數組origin存放原始資料，max_distance存放矩陣中的最大值，result存放最小生成樹的最大邊

    //opt存放節點和最小生成樹之間的最小距離

    int n,i,j,count,origin[500][500],opt[500],max_distance=0,min,vertex,result=0;

    //flag判斷是否已經加入到最小生成樹中

    bool flag[500];

    scanf("%d",&count);

    while(count-->0)

    {

        scanf("%d",&n);

        result=0; //result清零

//輸入origin，并記錄矩陣中的最大值

        for(i=0;i<n;i++)

        {

            for(j=0;j<n;j++)

            {

                scanf("%d",&origin[i][j]);

                if(origin[i][j]>max_distance)

                    max_distance=origin[i][j];

            }

        }

        //0号節點加入到生成樹中，目前最小距離為origin[0][i]的值       

        for(i=0;i<n;i++)

            opt[i]=origin[0][i];

//flag初始化，0節點先加入生成樹中，為true，其他為false

        flag[0]=true;

        for(i=1;i<n;i++)

            flag[i]=false;

        for(i=1;i<n;i++)   //循環n-1次，獲得n-1條邊

        {

            min=max_distance+1;

            for(j=0;j<n;j++)

            {

                if(!flag[j]&&min>opt[j])

                {

      //獲得不在生成樹中的最小的邊，記錄節點

                    min=opt[j];

                    vertex=j;

                }

            }

     //更新result和該節點的flag 

            if(result<min)

                result=min;

            flag[vertex]=true;

     //修改每個節點的opt 

            for(j=0;j<n;j++)

            {

                if(!flag[j])

                    opt[j]=origin[j][vertex]>opt[j]?opt[j]:origin[j][vertex];

            }

        }

        printf("%d/n",result);

    }

    return 1;

}

PKU1258Agri-Net和2485基本上是一模一樣，把result改為result+=min就過了，就不多說了。

相似類型的題目還有：http://acm.pku.edu.cn/JudgeOnline/problem?id=2395 （注意有重邊，是以每次輸入一條邊都要判斷它是否是這兩個點的最小邊。。）