Victordu

算法

普里姆:O(n*2) ,與圖中邊數(shù)無(wú)關(guān)，該算法適合于稠密圖.
1）設(shè)最小生成樹(shù)T的V（T）和E（T）均為空。
（2）從頂點(diǎn)集V（G）中任取一頂點(diǎn)加到頂點(diǎn)集V（T）中。??????????????????????
（3）在與V（T）中各頂點(diǎn)相關(guān)聯(lián)的所有邊中，取一條權(quán)值最小的邊（Vi，Vj）其中，Vi包含于V（T），Vj含于 V（T)。???????????????????????????????????
(4）將邊（Vi，Vj）加入到E（T）中，將頂點(diǎn)Vj到入到V（T）中.（5）若V（T）已滿(mǎn)n個(gè)頂點(diǎn)，則算法終止，否則轉(zhuǎn)步驟（3）。都是很典型很容易AC的
在這里挑一個(gè)最典型的題目貼上代碼

/**********************
Author: WHU_Victordu
Created Time: 2008-1-2
File Name: pku1258.cpp
? Description:?
???**************************/

#include <stdio.h>
#define MAXNUM 100000

int dis[101][101],low[101];

int main()
{
??? int n,i,j,min,k,sum;
?
??? while(scanf("%d",&n)!=EOF)
??? {
???????? sum=0;?????
?????? for(i=0;i<n;i++)
???????? for(j=0;j<n;j++)
???????? scanf("%d",&dis[i][j]);
??????
?????? for(i=0;i<n;i++)
?????? low[i]=dis[0][i];
???
????? low[0]=0;
?????
????? for(i=1;i<n;i++)
????? {
??????? min=MAXNUM;
??????? j=k=1;
???????
??????? while(j<n)
??????? {
????????? if(low[j]&&low[j]<min)
????????? {
??????????? min=low[j];
??????????? k=j;
????????? }
????????? j++;
??????? }
???????
??????? sum+=low[k];
???????
??????? low[k]=0;
???????
??????? for(j=1;j<n;j++)
??????? {
????????? if(dis[k][j]<low[j])
????????? low[j]=dis[k][j];
??????? }
????????
????? }
?????
????? printf("%d\n",sum);
?????
??? }
}