查找循環圖

Question

我試圖解決上面提出的問題，這裏的最小加權生成樹是我的嘗試：

嘗試：我們可以應用Dijkstra的最短路徑算法代替使用Prim's和Kruskal算法找到MST，因爲Dijkstra將訪問所有最小權重距離的節點。複雜性：對於G =（V，E），O（E日誌（V））

問題：

（1）我的做法正確嗎？ （2）這是問題的最有效答案嗎？

如果我完全錯了，我將不勝感激一個正確和有效的解決方案。

Answer 1

一個循環圖除了連接循環中的頂點外，不包含其他邊。因此，我們可以做的是遍歷所有N個邊，並消除最大加權邊形成包含邊的最小和的N-1個邊的生成樹，形成最小生成樹。