定义：最小生成树并不像数据结构中的树一样，而是从图演化而来，生成树有DFS生成树，BFS生成树，最小生成树等。
所谓最小生成树，就是在有N个节点的连通图中，找出N-1条边使N个点仍然连通，并且个边权值和最小。
代码如下：
/**********计算出图的最小生成树的代价，不能直达的点之间的权值设为100，假设所有点之间的
权值不超过99，代码暂时显示出生成树的路径貌似有bug*********/
#include<stdio.h>
#define M 6
void INIT_MAP(int map[][M]){
for(int i=0;i<M;i++){
for(int j=0;j<M;j++){
scanf("%d",&map[i][j]);
}
}
}
void SHOW_MAP(const int map[][M]){
for(int i=0;i<M;i++){
for(int j=0;j<M;j++){
printf("%d ",map[i][j]);
}printf("\n");
}
}
int procs(const int map[][M],int visit[][M-1]){
int res=0;
int ever[M]={0};
int low[M]={0};
int pos=0;
ever[0]=1;
for(int i=1;i<M;i++){
low[i]=map[pos][i];
}//随即从第一个节点开始访问
for(int i=1;i<M;i++){
//printf("%d-----",pos+1);
int max=100;
for(int j=0;j<M;j++){
if(ever[j]==0&&max>low[j]){
pos=j;
max=low[j];
}
}
visit[0][i-1]=max;
visit[1][i-1]=pos;
//printf("-----%d\n",pos+1);
ever[pos]=1;
//printf("%d\n",max);
res+=max;
for(int j=0;j<M;j++){
if(ever[j]==0&&low[j]>map[pos][j]){
low[j]=map[pos][j];
}
}
}
return res;
}
void SHOW_ROAD(const int map[][M],const int visit[][M-1]){
for(int i=0;i<M-1;i++){
for(int j=0;j<M;j++){
if(map[visit[1][i]][j]==visit[0][i]){
printf("%d",j+1);
}
}
//printf("%d",);
printf("-----%d\n",visit[1][i]+1);
}
}
void main(){
int map[M][M];
int visit[2][M-1]={0};
INIT_MAP(map);
int result=procs(map,visit);
//SHOW_MAP(map);
SHOW_ROAD(map,visit);
printf("最小生成树的权值是%d\n",result);
}
测试数据：
100 6 1 5 100 100
6 100 5 100 3 100
1 5 100 5 6 4
5 100 5 100 100 2
100 3 6 100 100 6
100 100 4 2 6 100