图的最小生成树



【需求分析】



若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。



（1）建立一个图，其存储方式可以采用邻接矩阵形式，需要定义两个数组，一个存储顶点，一个存储边，存储边的数组表明节点间的连通关系和边的权值；



（2）利用普里姆算法和克鲁斯卡尔算法求网的最小生成树；



（3）按顺序输出生成树中各条边以及它们的权值。



【算法描述】：



1 普里姆算法：以图中的节点为基础。从某一点出发，选择该点相连的边的最小边，直至图中所有节点都出现在生成树中。



2 克鲁斯克尔算法：以图中节点为基础。将图中的所有边按权值大小排列。从小到大依次选择边，知道这些边将所有节点都联通。-TheSmallTree