給定圖找到一個生成樹是不是最小

Question

如何找到一個生成樹這是不是最小的圖形（如果possiblr）

Answer 1

Kruskal algorithm發現最小生成樹重量，命令所有的邊緣，選擇他們從最輕到最重，並且只有在不形成循環時纔將其添加到解決方案中。當您達到等於頂點數減1的邊數時，您將擁有最小生成樹。

要獲得不是最小值的生成樹，只需應用相同的算法，而無需預先排序邊的列表，或者在開始之前隨機地亂序列表。

Answer 2

如果你的目標是找到任意的生成樹，不管它是否是最小的，你總是可以使用簡單的香草DFS或BFS來搜索圖形，通過添加新的邊緣來創建生成樹節點。它的運行時間與圖形大小呈線性關係，在實踐中速度很快，並且編碼起來很簡單。

如果您的目標是找到一個特別不是MST的生成樹，您可以考慮只運行一個常規MST算法，但在比較邊緣權重時，始終會反轉比較結果。這最終會找到最大的生成樹，除非圖中的每個生成樹碰巧最小，否則將不是最小生成樹。這需要與運行常規MST算法相同的時間，因此您可以選擇要使用哪一個算法。