最小生成树 prim算法实现c++.doc

最小生成树Prim算法实现的c ++语言,使用邻接矩阵存储边信息。共三个文件。
第一个
#ifndef __PRIM_H__
#define __PRIM_H__
template <class ElemType, class WeightType>
int MinVertex(const work<ElemType, WeightType> &net, int *adjVex)
// 操作结果:返回w,使得边<w, adjVex[w]>为连接V-U到U的具有最小权值的边
{
int w = -1; // 初始化最小顶点
int v; // 临时顶点
for (v = 0; v < (); v++)
{ // 查找第一个满足条件的V - U中顶点v
if ((v) == UNVISITED // 表示v为V - U中的顶点
&& (v, adjVex[v]) > 0) // 存在从v到U的边(v, adjVex[v])
{
w = v;
break;
}
}
for (v++; v < (); v++) // 查找连接V-U到U的具有最小权值的边<w, adjVex[w]>
if ((v) == UNVISITED && (v, adjVex[v]) >0 &&
(v, adjVex[v]) < (w, adjVex[w]))
w = v;
return w;
}
template <class ElemType, class WeightType>
void MiniSpanTreePrim(const work<ElemType, WeightType> &net, int u0)
// 初始条件:,u0为g的一个顶点
// 操作结果:用Prim算法从u0出发构造网g的最小代价生成树
{
if (u0 < 0 || u0 >= ()) throw Error("u0不合法1!");// 抛出异常
int *adjVex; // 如果v∈V-.GetWeight(v, adjVex[v])>0
// 表示(v, adjVex[v])是v到U具有最小权值边的邻接点
int u, v, w; // 表示顶点的临时变量
adjVex = new .GetVexNum()]; // 分配存储空间
for (v = 0; v < (); v++)
{ // 初始化辅助数组adjVex,并对顶点作标志,此时U = {v0}
if (v != u0)
{ // 对于v∈V-U
adjVex[v] = u0;
(v, UNVISITED);
}
else
{ // 对于v∈U
(v, VISITED);
adjVex[v] = u0;
}
}
for (u = 1; u < (); u++)
{ // .GetVexNum() - 1个顶点
w = , adjVex);
// 选择使得边<w, adjVex[w]>为连接V-U到U的具有最小权值的边
if (w == -1)
{ // 表示U与V-U已无边相连
return;
}
cout << "edge:(" << adjVex[w] << "," << w << ") weight:"
<<(w, adjVex[w])<< endl ; // 输出边及权值
(w, VISITED); // 将w并入U
for (int v = (w); v >= 0 ; v = (w, v))
{ // 新顶点并入U后重新选择最小边
if ((v) == UNVISITED && // v ∈V - U
((v, w) < (v, adjVex[v]) || // 边<v,w>的权值更小
(v, adjVex[v]) == 0) ) // 不存在边<v, adjVex[v]>
{ // <v, w>为新的最小边
adjVex[v] = w;
}
}