数据结构实验之最小生成树
数据结构与算法实验报告
最小生成树
姓名：孙瑞霜
一、实验目的
1、熟练掌握学习的每种结构及其相应算法；
2、理论联系实际，会对现实问题建模并设计相应算法。
3、优化算法，使得算法效率适当提高
二、实验要求：
1． 认真阅读和掌握教材上和本实验相关的内容和算法；
2． 上机将各种相关算法实现；
3． 实现上面实验目的要求的功能，并能进行简单的验证。
三、实验内容
认真学习 学习通->数据结构->资料->数据结构实验指导书–陈越版，从第二章进阶实验1~10中任选一个来实现，编写程序，输入给定的数据，能得到给定的输出。总结算法思想、画出流程图，并思考程序有无改进空间，如何改进。
三、算法描述
所谓最小生成树，就是在一个具有N个顶点的带权连通图G中，如果存在某个子图G’，其包含了图G中的所有顶点和一部分边，且不形成回路，并且子图G’的各边权值之和最小，则称G’为图G的最小生成树。
由定义我们可得知最小生成树的三个性质：
• 最小生成树不能有回路。
• 最小生成树可能是一个，也可能是多个。
• 最小生成树边的个数等于顶点的个数减一。
四、详细设计
五、程序代码
#include<stdio.h>
#include<stdlib.h>
#define ERROR -1
#define MaxVertexNum 1000
#define INFINITY 65535
typedef struct GNode *MGraph;
struct GNode{
int Nv;
int Ne;
int G[MaxVertexNum][MaxVertexNum];
};
void CreateGraph(MGraph Graph){
int i,j,k,weight;
//printf( “请输入顶点数和边数(输入格式为:顶点数, 边数):\n” );
scanf(“%d%d”,&Graph->Nv,&Graph->Ne);
for ( i = 0; i < Graph->Nv; i++ ){
for ( j = 0; j < Graph->Nv; j++ ){
Graph->G[i][j]=INFINITY;
}
}
//printf(“请输入每条边所连接的两个顶点，输入格式为（顶点1 顶点2）\n”);
for ( k = 0; k < Graph->Ne; k++ ){
scanf(“%d%d%d”,&i,&j,&weight);
Graph->G[i-1][j-1]=weight;
Graph->G[j-1][i-1]=weight;
}
}
int FindMin(MGraph Graph,int dist[]){
int V,MinV;
int MinDist=INFINITY;
for(V=0;V<Graph->Nv;V++){
if((dist[V]!=0)&&(dist[V]<MinDist)){
MinDist=dist[V];
MinV=V;
}
}
if(MinDist<INFINITY) return MinV;
else return ERROR;
}
int Prim(MGraph Graph){
int dist[MaxVertexNum];
int parent[MaxVertexNum];
int V,W;
int k;
int VCount=0;
int TotalWeight=0;
//初始化，默认初始点下标为0；
for(V=0;V<Graph->Nv;V++){
dist[V]=Graph->G[0][V];
parent[V]=0;
}
parent[0]=-1;
dist[0]=0;
VCount++;
//printf(“最小生成树的各条边：\n”);
while(1) {
V=FindMin(Graph,dist);
if(V==ERROR) break;
//dist[V];边的距离
//printf(” %d-%d-%d “,parent[V],V,dist[V]);
TotalWeight+=dist[V];
dist[V]=0;
VCount++;
for(W=0;W<Graph->Nv;W++){
if((dist[W])&&(Graph->G[V][W]!=INFINITY)){
if(Graph->G[V][W]<dist[W]){
dist[W]=Graph->G[V][W];
parent[W]=V;
}
}
}
}
if (VCount<Graph->Nv) return ERROR;
else return TotalWeight;
}
int main(){
MGraph Graph=(MGraph)malloc(sizeof(struct GNode));
CreateGraph(Graph);
printf(“%d”,Prim(Graph));
return 0;
}
六、测试和结果
七、用户手册
首先打开Dev,然后将代码粘贴到上面，先编译看是否编译成功，再根据下面测试的数据将代码运行后依次填入，便能得出相应的结果，当然也可以尝试用其他测试数据来测验一下，看看最后结果如何。