神马品牌网长集中学何少红:最小生成树 急需帮助！
来源：百度文库 编辑：神马品牌网 时间：2024/05/11 00:54:08
最小生成树是我数据结构最后的综合设计
对于各位高手是小菜一碟 希望大家帮我 感激不禁！
我需要代码和设计报告 重谢！ 追加100分！ 决不食言！
问题如下：
若要在n个城市间建设通信网路，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题
（1） 利用普里姆算法和克鲁斯卡尔算法求网的最小生成树。
（2） 以文本形式输出生成树中各条边以及他们的权值
上过数据结构实验课的人都应该写过这个报告
也许还有人保留着 拿来让我参考一下也好
对于各位高手是小菜一碟 希望大家帮我 感激不禁！
我需要代码和设计报告 重谢！ 追加100分！ 决不食言！
问题如下：
若要在n个城市间建设通信网路，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题
（1） 利用普里姆算法和克鲁斯卡尔算法求网的最小生成树。
（2） 以文本形式输出生成树中各条边以及他们的权值
上过数据结构实验课的人都应该写过这个报告
也许还有人保留着 拿来让我参考一下也好
普里姆算法描述：
假设 N＝(V，E)是一个带权图，TE是N上最小生成树中边的集合。算法从U＝{u0}(u0∈V)，TE＝{}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u，v) ∈E中找一条权值最小的边(u，v)并入集合TE，同时v并入U，直至U＝V为止。此时TE中必有n-1边，则T＝(V，{TE})为N的最小生成树。
为实现这个算法需附设一个辅助数组 closedge，以记录从U到V-U具有最小代价的边。对每个顶点vi∈V-U，在辅助数组中存在一个相应分量closedge[I-1]，它包括两个域，其中lowcost存储该边上的权：显然， closedge[I-1]．Lowcost＝Min{cost(u，vi)|uEU} vex域存储该边依附的在U中的顶点。
你认为有人会浪费自己的时间来给你写报告么？