数据结构电网建设造价计算二

1、Prim算法的基本思想是：首先从集合V中任取一顶点（例如去顶点v0犬匮渝扮）放入集合U中，这时U={ v0}，TE=NULL。然后找出所有一个顶点在集合U里，另一个顶点在集合V-U里的边，使权(u, v)(u∈U, v∈V-U)最小，将该边放入TE，并将顶点v加入集合U。

2、重复上诉操作直到U=V为止。这时TE中有n-1条边，T=(U, TE)就是G的一颗最小生成树。

3、假设图采用邻接矩扃渚释夭阵表示法表示，用一对顶点的下标（在顶点表中的下标）表示一条边，定义如下：typedef struct{int start_vex, stop vex; //边的起点和终点AdjType weight; //边的权}Edge;

4、在构造最小生成树的过程中定义一个类型为Edge的数组mst: Edge mst[n-1]；其中，n为网络中顶点的个数，算法结束时，mst中存放求出的最小生成树的n-1条边。

5、可以用带权的无向图（即无向网）表示这n个小区之间的电网连接。

6、其中顶点表示小区，权值表示城市之间电网建设的造价，构造一个无向网的最小生成树即是满足要求的最低电网连接造价方案。