prim程序C++表示

有三个包，可以在VC++软件上运行。，如下：

第一个：

#ifndef __PRIM_H__

#define __PRIM_H__

template <class ElemType, class WeightType>

int MinVertex(const AdjMatrixUndirNetwork<ElemType, WeightType>&net, int *adjVex)

// *** 作结果：返回w，使得边<w, adjVex[w]>为连接V-U到U的具有最小权值的边

{

int w = -1 // 初始化最小顶点

int v// 临时顶点

for (v = 0v <net.GetVexNum()v++)

{ // 查找第一个满足条件的V - U中顶点v

if (net.GetTag(v) == UNVISITED// 表示v为V - U中的顶点

&&net.GetWeight(v, adjVex[v]) >0) // 存在从v到U的边(v, adjVex[v])

{

w = v

break

}

}

for (v++v <net.GetVexNum()v++) // 查找连接V-U到U的具有最小权值的边<w, adjVex[w]>

if (net.GetTag(v) == UNVISITED &&net.GetWeight(v, adjVex[v]) >0 &&

net.GetWeight(v, adjVex[v]) <net.GetWeight(w, adjVex[w]))

w = v

return w

}

template <class ElemType, class WeightType>

void MiniSpanTreePrim(const AdjMatrixUndirNetwork<ElemType, WeightType>&net, int u0)

// 初始条件：存在网net,u0为g的一个顶点

// *** 作结果：用Prim算法从u0出发构造网g的最小代价生成树

{

if (u0 <0 || u0 >= net.GetVexNum()) throw Error("u0不合法1!")// 抛出异常

int *adjVex // 如果v∈V-U,net.GetWeight(v, adjVex[v])>0

// 表示(v, adjVex[v])是v到U具有最小权值边的邻接点

int u, v, w // 表示顶点的临时变量

adjVex = new int[net.GetVexNum()]// 分配存储空间

for (v = 0v <net.GetVexNum()v++)

{ // 初始化辅助数组adjVex，并对顶点作标志，此时U = {v0}

if (v != u0)

{ // 对于v∈V-U

adjVex[v] = u0

net.SetTag(v, UNVISITED)

}

else

{ // 对于v∈U

net.SetTag(v, VISITED)

adjVex[v] = u0

}

}

for (u = 1u <net.GetVexNum()u++)

{ // 选择生成树的其余net.GetVexNum() - 1个顶点

w = MinVertex(net, adjVex)

// 选择使得边<w, adjVex[w]>为连接V-U到U的具有最小权值的边

if (w == -1)

{ // 表示U与V-U已无边相连

return

}

cout <<"edge:(" <<adjVex[w] <<"," << w <<") weight:"

<<net.GetWeight(w, adjVex[w])<<endl // 输出边及权值

net.SetTag(w, VISITED) // 将w并入U

for (int v = net.FirstAdjVex(w)v >= 0 v = net.NextAdjVex(w, v))

{ // 新顶点并入U后重新选择最小边

if (net.GetTag(v) == UNVISITED && // v ∈V - U

(net.GetWeight(v, w) <net.GetWeight(v, adjVex[v]) || // 边<v,w>的权值更小

net.GetWeight(v, adjVex[v]) == 0) ) // 不存在边<v, adjVex[v]>

{ // <v, w>为新的最小边

adjVex[v] = w

}

}

}

delete []adjVex // 释放存储空间

}

#endif

内容太长，另两个传不上

你要先明白prim算法的原理，明白原理后看下面的程序要点：

1.程序实现的时候将点分成两部分，加入集合的和没有加入集合的；

2.每次从没有加入集合中找点；

3.对所有没有加入到集合中的点中，找一个边权最小的；

4.将边权最小的点加入集合中，并且修改和加入点相连的没有加入的点的权，重复第2步，知道所有的点都加入到集合中；

算法同样是解决最小生成树的问题。

其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。

与prim算法的不同：prim算法为单源不断寻找连接的最短边，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。

复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。

Prim算法用于求无向图的最小生成树

设图G =（V，E），其生成树的顶点集合为U。

①、把v0放入U。

②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。

③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。

其算法的时间复杂度为O(n^2)

Prim算法实现：

（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）

（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。

{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}

---