这是我做的第一个最小生成树的题目。算法思想就是从任意一个点出发,标记为已找到的。然后找到所有与已找到的点相连的边中,权值最小的边。把边的另一个顶点标记为已找到的。然后更新所有与这个刚找到的顶点相邻的顶点的信息。重复这个步骤,直到找到了n-1个顶点。那就组成了一棵最小生成树,就是题目结束了。
#include <stdio.h>
#define DEBUG 1
const int Max = 0x7fffffff ;
const int N = 30 ;
int n, map[N][N], dis[N], used[N] ;
int Prim( )
{
int i, j, index, len, min ;
len = 0 ;
for( i=1; i<=n; ++i ){
// 出发点定义为 1
dis[i] = map[1][i] ;
used[i] = 0 ;
}
// used[]数组作为标志 ,表示已经被标记过的点
used[1] = 1 ;
for( i=1; i<n; ++i ){
min = Max ;
//找到所有与已标记过的点相连的边中,权值最小的边
for( j=1; j<=n; ++j ){
if( !used[j] && min>dis[j] ){
index = j ;
min = dis[j] ;
}
}
used[index] = 1 ;
len += dis[index] ;
//更新所有与已找到的点相连的边的信息
for( j=1; j<=n; ++j ){
if( !used[j] && dis[j]>map[index][j] )
dis[j] = map[index][j] ;
}
}
return len ;
}
int main()
{
//输入输出的重定向
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
#endif
int i, j, d, geshu, weight ;
char ch, to ;
while( scanf("%d", &n) && n ){
//初始化数据
for( i=1; i<=n; ++i ){
for( j=1; j<=n; ++j ){
map[i][j] = Max ;
}
}
//读入数据
for( i=1; i<n; ++i ){
//吃掉空格,不然机会造成读入数据错误
getchar() ;
scanf("%c %d", &ch, &geshu ) ;
for( j=1; j<=geshu; ++j ){
scanf(" %c %d", &to, &weight ) ;
// -64 是为了把第一个点,也就是A点,当成第一个点
// 因为A的ASCII是65 ,所以65-64 就是 1
// 建立的是无向图
map[i][to-64] = map[to-64][i] = weight ;
}
}
printf("%d\n", Prim( ) ) ;
}
return 0 ;
}