關於最小生成樹圖

-4

是否有比Prime更好的算法（更優化，更快）？Kruskal's algorithms？關於最小生成樹圖

來源

2017-08-09 Saeed VA

https://en.wikipedia.org/wiki/Minimum_spanning_tree#Faster_algorithms – DAle

Prime的算法和Kruskal算法的運行速度非常快，如果它實現的很好。嘗試爲您的數據集案例使用最佳數據結構。實際上，在大多數情況下，您並不需要更快的算法。

如果需要並行執行算法，則使用Borůvka's algorithm。

如果你需要理論最快的算法，比檢查Decision trees算法。

還有線性algorithm的特例。

來源

2017-08-09 12:57:34 knst

對於具有非常大輸入的複雜網絡，哪一個最適合？ –

對於具有V頂點E邊的圖，Kruskal算法運行在O（E log V）時間，Prim算法運行在O（E + V log V）攤平時間。所以，數E，V，並決定這是更好的。如果有很多頂點，但沒有太多的邊緣，比使用Prim的。如果有更多的頂點，比使用Kruskal。並且使用（或寫下自己的）這個算法的良好實現，因爲常量非常重要，糟糕的實現可能會非常緩慢。如果輸入真的很大，並且您擁有至少12個內核（或具有多個實例的羣集），則嘗試使用Boruvka的算法。 – knst

關於最小生成樹圖

回答

相關問題