Kruskal和Prim算法的应用程序

任何人都可以请给出两种算法的一些应用程序，哪里以及哪些应用程序可用于？Kruskal和Prim算法的应用程序

来源

2011-09-06 vini

某处引用它们会很有用。 – Julian

首先研究了最小生成树的布线方式，以最小化布线总成本的方式布置电网。在最小生成树中，所有节点（房屋）将通过导线以最小成本和冗余（切断任何导线必须将电网切割成两块）的方式连接到电源。

从那以后，这个问题已经得到很好的研究，常常被用作更复杂算法的子程序。用于寻找旅行推销员问题的近似解的Christofides algorithm在关键步骤中使用它，以及用于查找斯坦纳树的一些算法。

最小生成树也被用于generate mazes。克鲁斯卡尔和普里姆的算法都以这种方式使用，通常创造出高质量的迷宫。

如果您对最小生成树问题，其应用程序及其算法的完整历史感兴趣，那么涵盖所有这些问题的确是非常出色的纸张。我强烈建议给它一个阅读！

希望这会有所帮助！

来源

2011-09-06 17:18:46 templatetypedef

引述维基百科：

一个例子是有线电视公司铺设光缆到一个新的社区。如果仅限于沿特定路径埋设电缆，则会有一个图形表示通过这些路径连接的点。其中一些路径可能更昂贵，因为它们更长，或者需要将电缆埋在更深处;这些路径将由具有较大权重的边表示。该图的生成树将是那些没有周期但仍连接到每个房屋的路径的子集。可能有几种生成树。最小生成树将是总成本最低的树。

来源：http://en.wikipedia.org/wiki/Minimum_spanning_tree

来源

2011-09-06 13:20:27 Simone

首先你必须明白，无论普里姆的和Kruskal算法是在图中寻找有用Minimum spanning Tree。最小生成树的实际应用之一，我能想到的是以最小的成本连接同一家公司的不同办公室。

来源

2011-09-06 13:27:10