prim 算法實(shí)現(xiàn)
# include<stdio.h>
# include<limits.h>
const int maxn = 1000 ;
typedef int Graph[maxn][maxn];
Graph G;
int cost;
int lowdest[maxn],used[maxn];
int prim(Graph G,int n)
{
int min,k = 0,i,j;
used[0] = 1;
lowdest[0] = 0;
for(i = 1 ; i < n ; i ++)
{
lowdest[i] = G[i][0];
used[i] = 0;
}
for(i = 1; i < n ; i ++)
{
min = INT_MAX;
for(j = 0; j < n ; j ++)
{
if(!used[j]&&lowdest[j] < min)
{
min = lowdest[j];
k = j;
}
}
used[k] = 1;
cost += min;
for(j = 0; j < n ; j++)
{
if(!used[j] && G[j][k]<lowdest[j])
lowdest[j] = G[j][k];
}
}
return 0;
}
int main()
{
int N,i,j,M;
int x,y;
while(scanf("%d",&N),N)
{
scanf("%d",&M);
for(i = 0; i < N; i ++)
for(j = 0; j < N; j ++)
{
if(i == j)
G[i][j]= G[j][i] = 0;
else
G[i][j]= G[j][i] = 1;
}
cost = 0;
for(x =0; x< M;x++)
{
scanf("%d%d",&i,&j);
G[i-1][j-1]= G[j-1][i-1] = 0;
}
prim(G,N);
//if(M == 0) cout<<N-1<<endl;
//else
printf("%d\n",cost);
}
return 0;
}
posted on 2010-10-21 16:46
付翔 閱讀(160)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM 數(shù)據(jù)結(jié)構(gòu)