只有葉子的最小生成樹？

我被要求編寫一個算法，在圖G中找到最小生成樹，但條件是G的每個頂點都是生成樹T中的一個假。如果圖有多個2個元素？假設G包含頂點a，b和c，生成樹可能類似於a-b-c，所以在這種情況下b不是葉。只有葉子的最小生成樹？

我不是在尋找一種算法的解決方案，我只想了解一棵生成樹如何僅由樹葉組成。

這是問題的確切措辭

感謝您的幫助

在這裏評論，所以其他人不會感到困擾：我不能在問題陳述中看到成本c_e必須完全不同。如果情況是這樣的話，那麼問題就不復存在了，因爲有一個獨特的MST，你的問題就會奏效。但是，我不認爲這是問題的本意。 – ead

的問題指出，S是在圖中的頂點V的子集。可能有非葉節點。但是，你必須確保這些內部節點不在S中。如果S等於V，那麼你是對的。

2016-02-14 21:11:31 lex82

謝謝，我最終做的是使用Boruvka獲取MST，然後遍歷每個節點並將它們與集合中的頂點進行比較。如果它們相同，我檢查節點是否沒有孩子，否則MST不可行。 – user1354784

@ user1354784我不認爲你的方法可行，因爲MST不是唯一的，你不能確定，Boruvka（或任何其他標準算法）會選擇正確的MST。可以有一些MST滿足關於樹葉的約束，而另一些則沒有。 – ead

我認爲我們可以假設所有的邊都有不同的值 – user1354784

回答