最小生成树 prim算法实现(利用图的邻接矩阵来存放图)

时间:2021-06-06 09:55:23

定义:最小生成树并不像数据结构中的树一样,而是从图演化而来,生成树有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