是否有比Prime更好的算法(更優化,更快)?Kruskal's algorithms?關於最小生成樹圖
關於最小生成樹圖
回答
Prime的算法和Kruskal算法的運行速度非常快,如果它實現的很好。嘗試爲您的數據集案例使用最佳數據結構。 實際上,在大多數情況下,您並不需要更快的算法。
如果需要並行執行算法,則使用Borůvka's algorithm。
如果你需要理論最快的算法,比檢查Decision trees算法。
還有線性algorithm的特例。
對於具有非常大輸入的複雜網絡,哪一個最適合? –
對於具有V頂點E邊的圖,Kruskal算法運行在O(E log V)時間,Prim算法運行在O(E + V log V)攤平時間。所以,數E,V,並決定這是更好的。如果有很多頂點,但沒有太多的邊緣,比使用Prim的。如果有更多的頂點,比使用Kruskal。並且使用(或寫下自己的)這個算法的良好實現,因爲常量非常重要,糟糕的實現可能會非常緩慢。如果輸入真的很大,並且您擁有至少12個內核(或具有多個實例的羣集),則嘗試使用Boruvka的算法。 – knst
- 1. 關於切入最小生成樹
- 2. 多重最小生成樹圖
- 3. 通用最小生成樹
- 4. 動態最小生成樹
- 5. 最快最小生成樹算法
- 6. 什麼是最小葉生成樹?
- 7. Java最小生成樹問題
- 8. 最小直徑生成樹算法
- 9. R:深度最小生成樹
- 10. Sollin的最小生成樹算法
- 11. Networkx最小生成樹 - 精度問題?
- 12. 有關最小生成樹的快速問題
- 13. 設計一個圖,其中最短路徑樹比最小生成樹長
- 14. 最小生成樹只有2等於邊緣
- 15. Java:使用JGraphT生成最小生成樹?
- 16. 有向圖的雙向最小生成樹
- 17. 查找具有最大最小度的生成樹
- 18. 使特定節點的程度最小化的最小生成樹
- 19. 約束度+有界直徑最小生成樹的算法?
- 20. 使用鄰接表來表示最小生成樹
- 21. 給定必須包含的邊的最小生成樹數
- 22. 最小生成樹切割後的聚類
- 23. Bluemix上的IBM Graph中的最小生成樹
- 24. 最小生成樹的運行時間? (Prim方法)
- 25. 兩條邊相連的最小生成樹
- 26. 具有K額外節點的最小生成樹
- 27. 如何使用Neo4j查找最小生成樹?
- 28. 我的最小生成樹實現中的錯誤
- 29. Python:如何可視化網絡的最小生成樹?
- 30. 這個最小生成樹算法是否正確?
https://en.wikipedia.org/wiki/Minimum_spanning_tree#Faster_algorithms – DAle