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