第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++;//处理下一条边;
}