在sparce圖上執行Kruskal算法的最佳數據結構？

Question

如果對空間沒有限制，那麼假定圖形將被打包，選擇什麼樣的預處理kruskals算法是最好的數據結構。

我想使用單鏈表實現

Answer 1

這聽起來像是從ECE 250在沃特盧大學的一名學生。不幸的是，項目截止日期已經結束。

Answer 2

是的。 :-)不幸的是，這個學生提出的問題很糟糕，因爲它沒有提供與手頭問題相關的其他操作的細節。如果圖表已經存在，那麼一大堆適合的圖表是合適的;然而，圖的構造是問題的一部分，所以根據重量以線性順序存儲邊更爲理想。使Kruskal的算法快得多。