vin*_*ini 11 algorithm prims-algorithm kruskals-algorithm
任何人都可以请给出这两种算法的一些应用程序,它们可以用于哪些应用程序？
tem*_*def 19
首先研究最小生成树,以便以最小化布线总成本的方式布置电网.在最小生成树中,所有节点(房屋)将以最小成本和冗余的方式通过电线连接到电源(切割任何电线必须将电网切割成两块).
从那以后,这个问题得到了很好的研究,并且经常被用作更复杂算法的子程序.用于寻找旅行商问题的近似解的Christofides算法在关键步骤中使用它,一些用于查找Steiner树的算法也是如此.
最小生成树也被用于生成迷宫.Kruskal和Prim的算法都以这种方式使用,通常可以创建高质量的迷宫.
如果您对最小生成树问题,其应用程序及其算法的完整历史感兴趣,可以在此处获得涵盖所有这些的真正优秀的论文.我强烈建议你阅读!
希望这可以帮助!