数据结构—最小生成树.docx

数据结构—最小生成树.docx实验：最小生成树
一、 程序设计简介
本验证程序实现了 Prim算法。程序提供图的创建和用Prim求最小生成树。图的存储采 用了数组存储。运行结果输出创建的图信息及求得的最小生成树。
二、 源程序
(1 )Minitree_prim= w;// <v2, vl>
}
= 3;
return true;
}
template <class T>
void MGraph<T>::DestroyGraph()// 销毁图
for(int i = 0 ;i<;i++)
for(int j = i+1 ;j<;j++)
if( [i] [j] .info) {
delete [][i][j].info;
mgraph. arcs [i][j]. info = mgraph. arcs [j][i]. info = false; }
}
= 0;
= 0;
}
template <class T>
int MGraph<T>::Locate Vex(T u)〃确定顶点在图中的位置
(
for(int i = 0 ;i<MAX_VERTEX_NUM;i++)
{
if(u == [i])
(
return i;
}
}
return -1;
}
template <class T>
int MGraph<T>::Minimum(miniside<T> SZ [MAX_VERTEX_NUM]) 〃求辅助数组sz中的lowcost的最小正值
{
int i = 0,min,k,j;
while(! SZ[i].lowcost)
(
i++；
)
min = SZ[i].lowcost;//找到第一个非 0 值
k = i;//k先存放第一个非0值的位置
for(j = i+1 ;j<;j++)
〃在第一个非0值之后开始依次寻找较小值并且记录位置
(
if(SZ[j] .lowcost>0)
{
if(min>SZ[j ] .lowcost)
〃找到较小值
min = SZ[j].lowcost;
k = j;〃记录较小值的位置
}
return k;
)
template <class T>
void MGraph<T>::MiniSpanTree_PRIM(T u) 〃用普利姆算法从顶点u开始构造网的最
小生成树，并输出各条边
{
int i,j,k;
miniside<T> closedge[MAX_VERTEX_NUM];
k = Locate Vex(u);
for(j = O;j<;j++)
〃初始化辅助数组
{
if(j!=k)
{
closedgefj ] .adj vex = u;
closedgefj ] .lowcost = mgraph. arc s [k] [j ]. adj;
}
}
closedge[k].lowcost = 0 ;〃初始化顶点集 U = {u}
cout«"最小生成树的各条边依次为：” v<endl;
for(i = 1 ;i<;i++)
〃期许 -1 个顶点
{
k = Minimum(closedge); 〃求出下一个结点的位置
cout«closedge[k].adjvex«n-n«[k]« ”权 值：
"«closedge[k] .lowcost «endl;
closedge[k].lowcost = 0;//将位置为k的顶点并入u集合
for(j = 0 ;j <;j ++)
〃新顶点并入u集后重新选择最小边
{
if( [k] [j ] .adj<closedge[j ] .lowcost)
{
closedge[j].adjvex 二 [k];
closedgefj ] .lowcost = [k] (j] .adj;
}
#endif
(2)
#include <iostream>
#include <string>
using namespace std;
#include "
void opeshow()
{