付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
prim 算法实现

# 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 付翔 阅读(116) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜