第1个回答 2010-12-24
若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。
（1）建立一个图，其存储方式可以采用邻接矩阵形式，需要定义两个数组，一个存储顶点，一个存储边，存储边的数组表明节点间的连通关系和边的权值；
（2）利用普里姆算法和克鲁斯卡尔算法求网的最小生成树；
（3）按顺序输出生成树中各条边以及它们的权值。
【算法描述】：
1 普里姆算法：以图中的节点为基础。从某一点出发，选择该点相连的边的最小边，直至图中所有节点都出现在生成树中。
2 克鲁斯克尔算法：以图中节点为基础。将图中的所有边按权值大小排列。从小到大依次选择边，知道这些边将所有节点都联通。
数据结构：
邻接矩阵（二维数组） 无向图（结构） 结构
【流程图】
主程序流程图
开始
创建图
调用prim算法
调用kruskul算法
结束
Prim伪码流程：
Prim(gragh g, char u)
{
辅助结构数组初始化；（点及其相连边最小权值结构数组）
初始一个节点；
For(i=1;i<g.arcnum;i++)
{
选择第i个顶点的最小相连边；
将另个顶点并入；
For(j=0;j<g.arcnum;j++)
新顶点并入后重新选择最小边；
}
}
Kruskul伪码流程：
Kruskul(graph g)
{
用邻接矩阵转换初始化 顶点边结构数组；
将顶点边结构数组按照边权值从小到大排列；
初始化顶点编号；
While(k<g.vexnum-1) //j,k初始为0
{
记录第几条边的两个顶点位置；
如果两个点的不再一个集合，则输出这条边；
For(i=0;i<g.vexnum-1;i++)
合并各条边的标记；
J++;//处理下一条边；
}