算法使用DFS

Question

找到一個MST

我有以下算法：對於在邊緣上給定的（有限無向簡單）圖G =（V，E）具有正權重函數：

1. 運行DFS（深度 - 首先搜索），直到您發現邊緣倒退或DFS停止。如果停止，返回G.
2. 在一個由倒退邊緣構造的圓形發現的最重的邊緣，距離G.刪除
3. 返回1.

現在我需要明白這是什麼算法在做。我已經證明算法給了我一個G的生成樹，我相信它是一棵最小生成樹，但我未能證明這一點。請幫我證明一下。

Answer 1

證明當e是G的週期中最重的邊時，G-e的MST的成本不會大於G的MST的成本（設T是G的MST並使用T和關於e構造G-e的生成樹T'的假設，其成本（T'）≤cost（T）。）在| E |算法產生一個MST。

Answer 2

看起來您正在執行reverse-delete algorithm的變體，但您仍然必須證明您的算法與刪除所有不會斷開圖形的最高加權邊的等效操作是等價的。