随笔 - 87  文章 - 279  trackbacks - 0
<2006年6月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 191917
  • 排名 - 117

最新评论

阅读排行榜

评论排行榜

 

const   int  CNST_NumGrphNodes  =   101 ;
// 最小生成树元素
struct  TTreeEdge  {
    
int  v1, v2; 
    
double  w;
}
;
// 候选集元素
struct  TCloseRec  {
    
double  lowCost;
    
int  vec;
}
;
int  MST_prim( int  g[][CNST_NumGrphNodes],  int  n, TTreeEdge  * minTree)  {
    
int  i, j, k;
    TCloseRec 
* close  =   new  TCloseRec[n];    
    
for  (i = 1 ; i < n; i ++ {
        close[i].vec 
=   0 ;
        close[i].lowCost 
=  g[i][ 0 ];
    }

    close[
0 ].lowCost  =   - 1 ;
    
for  (i = 0 ; i < n - 1 ; i ++ {
        
// 找图点
         for  (k = 1 ; k < n; k ++ {
            
if  (close[k].lowCost  !=   - 1 {
                
break ;
            }

        }

        
for  (j = k + 1 ; j < n; j ++ {
            
if  (close[j].lowCost  !=   - 1 {
                
if  (close[j].lowCost  <  close[k].lowCost)  {
                    k 
=  j;
                }

            }

        }

        
// 加入树中
        minTree[i].v1  =  k;
        minTree[i].v2 
=  close[k].vec;
        minTree[i].w 
=  close[k].lowCost;
        close[k].lowCost 
=   - 1 ;
        
// 调整候选集
         for  (j = 1 ; j < n; j ++ {
            
if  (close[j].lowCost  >  g[j][k])  {
                close[j].lowCost 
=  g[j][k];
                close[j].vec 
=  k;
            }

        }

    }

    delete []close;
    
return   0 ;
}
posted on 2006-05-01 12:06 阅读(2819) 评论(3)  编辑 收藏 引用 所属分类: 数据结构与算法

FeedBack:
# re: 最小生成树prim算法 2006-06-13 19:10 sss
#include <stdio.h>

#define inf 9999

#define max 40

prim(int g[][max],int n)

{int lowcost[max],closest[max];

int i,j,k,min;

for(i=2;i<=n;i++) //n个顶点,n-1条边

{lowcost[i]=g[1][i]; //初始化

closest[i]=1; //顶点未加入到最小生成树中

}

lowcost[1]=0; //标志顶点1加入U集合

for(i=2;i<=n;i++) //形成n-1条边的生成树

{min=inf;

k=0;

for(j=2;j<=n;j++) //寻找满足边的一个顶点在U,另一个顶点在V的最小边

if((lowcost[j]<min)&&(lowcost[j]!=0))

{min=lowcost[j];

k=j;

}

printf("(%d,%d)%d\t",closest[k],k,min);

lowcost[k]=0; //顶点k加入U

for(j=2;j<=n;j++) //修改由顶点k到其他顶点边的权值

if(g[k][j]<lowcost[j])

{lowcost[j]=g[k][j];

closest[j]=k;

}

printf("\n");

}

}





int adjg(int g[][max]) //建立无向图

{int n,e,i,j,k,v1,v2,weight;

printf("输入顶点个数,边的条数:");

scanf("%d,%d",&n,&e);

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

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

g[i][j]=inf; //初始化矩阵,全部元素设为无穷大

for(k=1;k<=e;k++)

{printf("输入第%d条边的起点,终点,权值:",k);

scanf("%d,%d,%d",&v1,&v2,&weight);

g[v1][v2]=weight;

g[v2][v1]=weight;

}

return(n);

}





void prg(int g[][max],int n) //输出无向图的邻接矩阵

{int i,j;

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

printf("%d\t",i);

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

{printf("\n%d\t",i);

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

printf((g[i][j]==inf)?"\t":"%d\t",g[i][j]);

}

printf("\n");

}





main()

{int g[max][max],n;

n=adjg(g);

printf("输入无向图的邻接矩阵:\n");

prg(g,n);

printf("最小生成树的构造:\n");

prim(g,n);

}

  回复  更多评论
  
# re: 最小生成树prim算法 2006-06-14 00:45 beyonlin
代码量的确小很多:)  回复  更多评论
  
# re: 最小生成树prim算法[未登录] 2008-05-13 20:52 sky
帅哥  回复  更多评论
  

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