創建圖形以強制Kruskal算法爲最壞情況

Question

我想在許多節點上創建grpah以在最壞情況下強制使用kruskal算法。它應該是什麼樣的圖形？我卡住了。

Answer 1

假如要實現克魯斯卡爾算法dijoint套，並且邊緣具有穩定和「快」的算法，你將有O（ē日誌E）最壞的情況下進行排序。你也可以有E = O（V^2），所以最壞的情況也會是O（E log V）。我們可以得出結論，運行時間由堆操作占主導地位，因此通常算法在考慮所有邊之前終止，在實踐中更快。考慮到所有這些，爲了重現最壞的情況所有你需要做的就是最大化你的圖形，考慮到每個頂點將有連接到所有其他頂點的邊緣。