xie
数据结构与算法实验
院 别： 年级专业： 姓 名： 学 号：
计算机科学与信息工程学院 2014级空间信息与数字技术
杨哲庆 1420012138
2015 年 12月
实验8 最小生成树 实验
8.1最小生成树
8.1.1实验的主要内容和目的
① 使用Prim算法建立最小生成树。
② 使用Kruskal算法建立最小生成树。
③ 编写一个能对邻接矩阵中的边进行自小到大的存储在数组中的算法；
8.1.2代码
MGraph.h (MGraph类的声明)
#if !defined(AFX_MGRAPH_H__FDC762FA_D8BE_473C_B917_CA2693733E3F__INCLUDED_) #define AFX_MGRAPH_H__FDC762FA_D8BE_473C_B917_CA2693733E3F__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
const int Max=20; //图中最多顶点的个数
const int MaxSide=100; //图中最多的边数
const int infinite=9999; //infinite假设为无限大
struct element //辅助结构体element
{
int lowcost; //候选最短边的邻接点
int adjvex; //候选最短边的权值
};
struct EdgeType //辅助结构体EdgeType
{
int from,to; //边依附的两个顶点
int weight; //边上的权值
};
template<class T>
class MGraph
{
public:
MGraph();
void Prim();
void buildEdge(); //建立边集数组存储边，由小到大
void Kruskal();
int MinEdge(element a[]); //查找最小权值
int FindRoot(int parent[],int v);
private:
T vertex[Max]; //存放图中顶点信息的数组 int arc[Max][Max]; //邻接矩阵数组
int vertexNum,arcNum; //顶点数和边数
EdgeType edge[MaxSide]; //实例化边集数组 element shortEdge[Max]; //实例化辅助数组 };
#endif
MGraph.cpp (MGraph类的实现)
#include<iostream>
using namespace std;
#include "MGraph.h"
template<class T>
MGraph<T>::MGraph()
{
int i,j;
cout<<"请输入顶点的个数vertexNum："<<" ";
cin>>vertexNum;
cout<<"请输入边的条数arcNum："<<" ";
cin>>arcNum;
for(i=0;i<vertexNum;i++)
{
cout<<"请输入第"<<i+1<<"个顶点的信息"<<"\t"; cin>>vertex[i];
}
for(i=0;i<vertexNum;i++)
for(j=0;j<vertexNum;j++)//初始化图的邻接矩阵 arc[i][j]=infinite;
for(int k=0;k<arcNum;k++) //存储图的边信息
{
int m,n,weight;
cout<<"请输入边的两个顶点的序号：";
cin>>m>>n;
cout<<"请输入("<<m<<","<<n<<")的权值："; cin>>weight;
arc[m][n]=weight;
arc[n][m]=weight;
}
}
template<class T>
int MGraph<T>::MinEdge(element a[]) //查找最小权值 {
int temp,min=infinite;
for(int i=0;i<vertexNum;i++)
if( min>shortEdge[i].lowcost && shortEdge[i].lowcost!=0 )
{
min=shortEdge[i].lowcost;
temp=i;
}
return temp;
}
template<class T>
void MGraph<T>::Prim()
{
int i,j,k;
for(i=1;i<vertexNum;i++) //初始化辅助数组 shortEdge {
shortEdge[i].lowcost=arc[0][i];
shortEdge[i].adjvex=0;
}
shortEdge[0].lowcost=0; //将顶点0加入集合U
for(i=1;i<vertexNum;i++) //重复下列操作vertexNum-1次
{
k=MinEdge(shortEdge); //寻找最短边的领结点k
cout<<"("<<k<<","<<shortEdge[k].adjvex<<")"<<shortEdge[k].lowcost<<endl; shortEdge[k].lowcost=0; //将顶点k加入集合中
for(j=1;j<vertexNum;j++) //调整数组shortEdge[n]
if(arc[k][j]<shortEdge[j].lowcost)
{
shortEdge[j].lowcost=arc[k][j];
shortEdge[j].adjvex=k;
}
}
}
template<class T>
void MGraph<T>::buildEdge()
{
int min=infinite;
int i,j;
int count=0;
EdgeType temp; //temp用于临时储存最小值
for(count=0;count<arcNum;count++) //用于寻找最小值
{
for(i=0;i<vertexNum;i++)
for(j=i+1;j<vertexNum;j++)
if( arc[i][j]<min && arc[i][j]!=0 ) //将值与min进行比较
{
min=arc[i][j]; //如若比min小 则将值赋予min
temp.from=i; //将所有信息赋予temp
temp.to=j;
temp.weight=arc[i][j];
}
arc[temp.from][temp.to]=0; //将最小值标记为0 在下次for循环中不会参与判断 edge[count].from=temp.from; //将最小值插入edge数组
edge[count].to=temp.to;
edge[count].weight=temp.weight;
min=infinite; //初始化min
}
}
template<class T>
void MGraph<T>::Kruskal()
{
int *parent=new int[vertexNum]; //创建一个parent数组
for(int i=0;i<vertexNum;i++)
parent[i]=-1;
int num=0,vex1,vex2;
for(i=0;i<arcNum;i++)
{
vex1=FindRoot(parent,edge[i].from);
vex2=FindRoot(parent,edge[i].to);
if(vex1!=vex2)
{
cout<<"("<<edge[i].from<<","<<edge[i].to<<")"<<edge[i].weight<<endl;//输出加入的边 parent[vex2]=vex1; //合并生成树
num++;
if( num==vertexNum-1)
return;
}
}
}
template<class T>
int MGraph<T>::FindRoot(int parent[],int v)
{
int t;
t=v;
while(parent[t]>-1) //求顶点t的双亲一直到根结点
t=parent[t];
return t;
}
test.cpp(主函数测试文件)
#include<iostream>
using namespace std;
#include"MGraph.cpp"
int visited[Max]={0};
int main()
{
MGraph<int> graph;
cout<<"最小生成树是:"<<endl;
cout<<"==========Prim算法=========="<<endl;
graph.Prim();
cout<<endl;
cout<<"==========Kruskal算法=========="<<endl;
graph.buildEdge();
graph.Kruskal();
cout<<endl;
return 0;
}
8.1.3总结
（1）实验过程中遇到的三个有意义的错误。
a. 编译器无错误提示，运行程序，出图1-1所示的乱码。
图1-1
如图1-2所示，在3个for循环中min只被赋值了一次，这会造成在
内层的两个for循环结束后，min中的值始终还保留。这样放入edge数组中的最小值始终相同，无法依次取出最小值放入edge数组中。
图1-2
如图1-3所示，在最内层2个for循环外将min再次初始化为无穷大，
这样不会影响第一层循环的最小值选取。
图1-3
再次运行程序得到图1-4所示结果，kruskal能够显示出5条边了，但结果是错误的。
图1-4
b. 接着分析图1-4所示错误。不仅边不对，而且权值也为乱码。
设置断点进行调试，找到出错位置，如图2-1所示。看似无错误，原来是对邻接矩阵中没有连通的顶点没有初始化，只对相邻的顶点进行赋值。
图2-1
在构造函数MGraph()中加入如图2-2所示代码，对邻接矩阵进行初始化，将所有顶点的之间相连的权值赋为inifinite(其中infinite为9999，相对其他边的权值为无限大)。
图2-2
再次运行程序，所得乱码消失，如图2-3所示。
图2-3
c. 虽然图2-3所示运行的结果中没有乱码，而且Prim算法运行正确，但是kruskal算法所得第五条边是错误的结果。由于输出错误，所以从如图3-1所示代码中分析。
图3-1
正确输出应该是(4,5)26，但实际输出的是(3,5)25，说明错误可能有两种。 ①edge[i].from这串代码所得到的值是错误的。
②if(vex1!=vex2)中的vex1和vex2值错误，导致了错误的判断。
通过调试建立edge数组的函数buildEdge()，函数如图3-2所示，一步一步观察，发现这个函数没有出问题，那么问题应该出在vex1和vex2的初始化。
图3-2
调试发现，FindRoot函数中的寻找双亲结点只执行了一次。而5号顶点距离根结点的路径长度为2，把错误的顶点号赋给了vex2，导致错误。错误原因如图3-3所示。
图3-3
将“if”改为“while”如图3-4所示。
图3-4
再次运行程序，得到正确的结果如图3-5所示。
图3-5
（2）实验过程使用的主要知识点。
a. 建立无向图的邻接矩阵存储；
b. 对建立的无向图，使用Prim算法生成最小生成树；
c. 对建立的无向图，使用Kruskal算法生成最小生成树；
（3）实验中遇到的不理解或体会比较深的问题。
a. Kruskal这个算法相对于Prim算法，更难实现。而Kruskal算法中我个人认为最核心，同时也是最难的是将邻接矩阵中的边，以权值为条件，从小到大的放入数组中。
为什么说这个边集存储数组是核心，是因为kruskal算法思想是将独立的顶点又权值最小的边开始，权值不断增大同时将双亲顶点不同的顶点相连接。
b. 在编写edge边集数组，我想到了2种方式来将权值从小到大的进行排序。
第一种是冒泡排序法，第二种是利用3个循环，最内层的两个循环用来遍历邻接矩阵找出最小值后，将其标记，使得下次遍历的时候不会再遍历到该值。
冒泡排序法我写完以后出现了一点小问题，研究了很久还是没有解决，于是便采用了第二种方法。第二种方法刚开始时，当一个值比min小的，我便将其标记为0，结果发现这会导致一个情况就是：假设arc[2][3]比min小min=arc[2][3] arc[2][3]=0，而后arc[2][4]又小于min arc[2][4]=0。这会导致在对邻接矩阵进行一次遍历就有许多条边会被标记为0，而不是理想情况下每遍历一次，便将所有值中的最小值标记为0。于是我设置了个temp变量，当arc[i][j]<min，则将所有信息赋给temp，之后在最内层的两个循环外再通过temp的值找到邻接矩阵中的最小点，将其标记为0。
c. 这次实验中经常发生逻辑错误，就是代码没有错，但是运行后得到的结果总是不对。每次碰到这种情况就不得不对代码进行调试，再观察一步一步的结果，与预期结果相比较才能找出错误原因。但我发现大多数错误都是因为没有对变量初始化。在MinEdge()和buildEdge()这两个函数中，两次因为min
没有初始化为infinite，所以耗费了大量的时间来检查错误。
这次实验的算法相对于前几次复杂了许多，所以检查错误也浪费了大量时间，而错误大多都因为忘记初始化，不免感慨自己太粗心。同时也感受到编程需要极其严密的逻辑思维，一个环节出错，整个程序都会受到影响。
第二篇：Prim最小生成树 实验报告含源码
实验报告
题目说明：POJ2395 Out of Ray
题目大意：Beth有m个农场，农场之间有些相通，有些不通。已知，Beth每一英里要一盎司的水，Beth希望走遍所有的农场但携带最少的水。问：Beth最多需要带多少水？（每个农场都可以补充水）
本程序利用Prim算法俩实现题目要求。
1.<创建>
输入农场数和农场之间的距离（均为整数），程序给出连通判断。
2.修改路径
按格式输入修改值，此时路线可能会改变。
3.<输出最大携带水量>，附上最小生成树
实验说明：
1. 基本思想
利用邻接表G [ ][ ] 储存农场信息，然后使用Prim算法来完成最小生成树的构建；最后寻找出最大边，如果农场是不连通的将给出提示，可以对路径修改。
2. 函数模块
（1） int InitiTable(int G[][MaxFarm],int num);//创建邻接表，返回值是农场数目
{
int j,k,TempValue;
while(true)
{
cout<<"请输入农场的数目:"<<' ';
cin>>num;
if(num<=MaxFarm&&num>0)
break;
cout<<"错误！请重新输入."<<endl<<endl;
}
for(j=0;j<num;j++)
{
for(k=0;k<num;k++)
{
if(j==k)
G[j][k]=MaxWeight;
else if(j<k)
{
while(true)
{
cout<<"请输入农场"<<j+1<<"至农场"<<k+1<<"的距离。如果该路不存在请输入-1："<<endl;
cin>>TempValue;
if(TempValue>=-1&&TempValue<MaxWeight) break;
cout<<"输入无效，请重新输入。"<<endl;
}
if(TempValue==-1)
TempValue=MaxWeight;
G[j][k]=G[k][j]=TempValue; //保持无向图矩阵的对称性
}
}
}
return num ;
}
（2） int LinkJudge(int G[][MaxFarm],int num);//连通的判断
{
int linkjug,j,k;
for(j=0;j<num;j++)
{
linkjug=0;
for(k=0;k<num;k++)
if(G[j][k]<MaxWeight)
{linkjug=1;break;}
if(linkjug==0)
break;
}
if(!linkjug)
cout<<"农场是不连通的，无法计算！"<<endl;
return linkjug;
}
（3）void find(int G[][MaxFarm],int in[],int num, int path[MaxFarm][2]);
{ //这是主要的函数，用来生成最小生成树
int start=0,i,j,k,v1,v2,min=MaxWeight;
while(true)
{
cout<<"请选择出发农场:"<<endl;
cin>>start;
if(start>0 &&start<=num)
break;
cout<<"输入错误！请确认后重新输入."<<endl<<endl;
}
in[start-1]=1;
for(i=0;i<num-1;i++)//这里只进行num-1次的循环，即对剩下num-1个数说明
{
for(j=0;j<num;j++)
for(k=0;k<num;k++)//对结点的每个连通值进行判断
if(G[j][k]<min&&in[j]&&(!in[k]))
//（判断有连通值 ；进行第二次时判断连接的值没被标记；判断本身未标记；）
{v1=j;v2=k;min=G[j][k];}//记录最小值min，一次循环后可知最小值
if(!in[v2])
{
path[i][0]=v1;
path[i][1]=v2;
in[v1]=1;
in[v2]=1;
min=MaxWeight;
}
}
}
（4）void Modify(int T[][MaxFarm],int num);//修改
{ int j,k,t1,t2,t3;//t1,t2,t3是修改用的
cout<<"现有路径如下："<<endl;
for(j=0;j<num;j++)
{ for(k=0;k<num;k++)
{ if(k%5==0 &&k!=0)cout<<endl;
if(T[j][k]==100) cout<<j+1<<"-"<<k+1<<":None\t";
else cout<<j+1<<"-"<<k+1<<":"<<T[j][k]<<" \t";}
cout<<endl<<"-----------------------------------------------------------------"<<endl;
}
cout<<"<修改>格式(不存在请输入-1)：1-2:-1 (路径长度)"<<endl;
while(true)
{scanf("%d-%d:%d",&t1,&t2,&t3);if(t3>=-1&&t3<MaxWeight) break;
cout<<"输入无效，请重新输入。"<<endl;}
if(t3==-1)//说明：如果距离为-1，则输出为none，不连通
T[t1-1][t2-1]=T[t2-1][t1-1]=MaxWeight;
else
T[t1-1][t2-1]=T[t2-1][t1-1]=t3;
//保持无向图矩阵的对称性
if(T[t1][t2]==100) cout<<"修改成功!农场"<<t1<<"至农场"<<t2<<"距离为:None(100)\t\n";
else cout<<"修改成功!农场"<<t1<<"至农场"<<t2<<"距离为"<<T[t1-1][t2-1]<<endl<<endl;
for(j=0;j<num;j++)
{ for(k=0;k<num;k++)
{ if(k%5==0 &&k!=0)cout<<endl;
if(T[j][k]==100) cout<<j+1<<"-"<<k+1<<":None\t";
else cout<<j+1<<"-"<<k+1<<":"<<T[j][k]<<" \t";}
cout<<endl<<"------------------------------------------------------------------"<<endl;
}
}//
（4）void Display(int G[][MaxFarm],int path[MaxFarm][2],int num);//输出
{ int i,max=0;
cout<<"最小生成树是："<<endl;
for(i=0;i<num-1;i++)
cout<<"农场"<<path[i][0]+1<<"至农场"<< path[i][1]+1<<endl;
for(i=0;i<num-1;i++)
{if(G[path[i][0]][path[i][1]]>max;max=G[path[i][0]][path[i][1]];}
cout<<"携带最大水量是："<<' '<<max<<endl;
}
[ 源代码 ]
#include "iostream"
using namespace std;
#define MaxFarm 10
#define MaxWeight 100
int InitiTable(int G[][MaxFarm],int num);
int LinkJudge(int G[][MaxFarm],int num);
void find(int G[][MaxFarm],int in[],int num, int path[MaxFarm][2]);
void Display(int G[][MaxFarm],int path[MaxFarm][2],int num);
void Modify(int T[][MaxFarm],int num);
void main()
{
start: int G[MaxFarm][MaxFarm],in[MaxFarm]={0},path[MaxFarm][2];//in[]为标记，path[]为最短路径记录
int num=0,linkjug=0; /*全局*/ int ch;//选择
do{
printf("\t $ 道-路-选-择 $\t\n");
printf("******************************************************************\n");
printf("\t1.创建 \t");printf("2.修改路径\t"); printf("3.携带最大水量\n");
printf("\t4.退出\t\n");
printf("******************************************************************\n");
printf("请输入功能的号码:");
scanf("%d",&ch);
switch(ch)
{
case 1: num=InitiTable(G,num);
linkjug=LinkJudge(G,num);
system("pause"); system("cls"); break;
case 2: Modify(G,num);
linkjug=LinkJudge(G,num);
system("pause");system("cls"); break;
case 3: linkjug=LinkJudge(G,num);
if(!linkjug) { system("pause");system("cls");break;}
find(G,in,num,path);
Display(G,path,num);
system("pause"); system("cls"); break;
case 4: system("exit"); exit(0);
default:system("cls");
goto start;
}
}while(1);
}
int InitiTable(int G[][MaxFarm],int num)//只处理为一个指针，可同名
{
int j,k,TempValue;
while(true)
{
cout<<"请输入农场的数目:"<<' ';
cin>>num;
if(num<=MaxFarm&&num>0)
break;
cout<<"错误！请重新输入."<<endl<<endl;
}
for(j=0;j<num;j++)
{
for(k=0;k<num;k++)
{
if(j==k)
G[j][k]=MaxWeight;
else if(j<k)
{
while(true)
{
cout<<"请输入农场"<<j+1<<"至农场"<<k+1<<"的距离。如果该路不存在请输入-1："<<endl;
cin>>TempValue;
if(TempValue>=-1&&TempValue<MaxWeight) break;
cout<<"输入无效，请重新输入。"<<endl;
}
if(TempValue==-1)
TempValue=MaxWeight;
G[j][k]=G[k][j]=TempValue; //保持无向图矩阵的对称性
}
}
}
return num ;
}
//////////////////////////////////////////////////////////////////////////////////////////////
void find(int G[][MaxFarm],int in[],int num, int path[MaxFarm][2])//寻找最小生成树
{
int start=0,i,j,k,v1,v2,min=MaxWeight;
while(true)
{
cout<<"请选择出发农场:"<<endl;
cin>>start;
if(start>0 &&start<=num)
break;
cout<<"输入错误！请确认后重新输入."<<endl<<endl;
}
in[start-1]=1;
for(i=0;i<num-1;i++)//这里只进行num-1次的循环
{
for(j=0;j<num;j++)
for(k=0;k<num;k++)
if(G[j][k]<min&&in[j]&&(!in[k]))
{
v1=j;
v2=k;
min=G[j][k];
}
if(!in[v2])
{
path[i][0]=v1;
path[i][1]=v2;
in[v1]=1;
in[v2]=1;
min=MaxWeight;
}
}
}
///////////////////////////////////////////////////////////////////////////////////////
void Display(int G[][MaxFarm],int path[MaxFarm][2],int num)
{
int i,max=0;
cout<<"最小生成树是："<<endl;
for(i=0;i<num-1;i++)
cout<<"农场"<<path[i][0]+1<<"至农场"<< path[i][1]+1<<endl;
for(i=0;i<num-1;i++)
{
if(G[path[i][0]][path[i][1]]>max)
max=G[path[i][0]][path[i][1]];
}
cout<<"携带最大水量是："<<' '<<max<<endl;
}
/////////////////////
void Modify(int T[][MaxFarm],int num)
{
int j,k,t1,t2,t3;//t1,t2,t3是修改用的
cout<<"现有路径如下："<<endl;
for(j=0;j<num;j++)
{ for(k=0;k<num;k++)
{ if(k%5==0 &&k!=0)cout<<endl;
if(T[j][k]==100) cout<<j+1<<"-"<<k+1<<":None\t";
else cout<<j+1<<"-"<<k+1<<":"<<T[j][k]<<" \t";}
cout<<endl<<"-----------------------------------------------------------------"<<endl;
}
cout<<"<修改>格式(不存在请输入-1)：1-2:-1 (路径长度)"<<endl;
while(true)
{
scanf("%d-%d:%d",&t1,&t2,&t3);
if(t3>=-1&&t3<MaxWeight) break;
cout<<"输入无效，请重新输入。"<<endl;
}
if(t3==-1)
T[t1-1][t2-1]=T[t2-1][t1-1]=MaxWeight;
else
T[t1-1][t2-1]=T[t2-1][t1-1]=t3;
//保持无向图矩阵的对称性
if(T[t1][t2]==100) cout<<"修改成功!农场"<<t1<<"至农场"<<t2<<"距离为:None(100)\t\n";
else cout<<"修改成功!农场"<<t1<<"至农场"<<t2<<"距离为"<<T[t1-1][t2-1]<<endl<<endl;
for(j=0;j<num;j++)
{ for(k=0;k<num;k++)
{ if(k%5==0 &&k!=0)cout<<endl;
if(T[j][k]==100) cout<<j+1<<"-"<<k+1<<":None\t";
else cout<<j+1<<"-"<<k+1<<":"<<T[j][k]<<" \t";}
cout<<endl<<"------------------------------------------------------------------"<<endl;
}
}
/////////////////////////////////////
int LinkJudge(int G[][MaxFarm],int num)
{
int linkjug,j,k;
for(j=0;j<num;j++)
{
linkjug=0;
for(k=0;k<num;k++)
if(G[j][k]<MaxWeight)
{
linkjug=1;
break;
}
if(linkjug==0)
break;
}
if(!linkjug)
{
cout<<"农场是不连通的，无法计算！"<<endl;
}
return linkjug;
}