最小生成树实验报告讲解.doc

xie
数据结构与算法实验
院 别：
计算机科学与信息工程学院
年级专业：
2014级空间信息与数字技术
姓 名：
杨哲庆
学 号：
1420012138
评语和成绩:
2015 年 12月
实验8 最小生成树 实验


① 使用Prim算法建立最小生成树。
② 使用Kruskal算法建立最小生成树。
③ 编写一个能对邻接矩阵中的边进行自小到大的存储在数组中的算法；

(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类的实现)
#include<iostream>
using namespace std;
#include ""
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;
f