查找所選頂點的最小生成樹的算法

Question

可以使用Prim算法或Kruskal算法來查找頂點/節點和邊/鏈接集合的最小生成樹/圖。我想要的是找到這個集合的最小生成圖的算法，但是生成的圖只需要包含任意選擇的節點，而不是所有的節點。如果結果圖包含的節點數多於所需數量，那麼這樣做沒問題。

這樣的算法是否存在？也許可以在修改圖形後僅使用Prim（或Kruskal's）算法來僅包含所需的節點？但是，我不確定如何在保持連通性的同時修改圖形。

例如，假設我們有形的起點圖（括號內的鏈接成本）鑽石：

A 
(2)/ \(1) 
    B C 
(2)\ /(5) 
    D 

現在，我們隨意決定，只有節點A和需要d。如果我們從A開始，我們仍然希望它走左邊的路徑，因爲（（2 + 2）<（1 + 5））。

說我們修改略圖：

A 
(2)/ \(1) (2) 
    B C ------E 
(2)\ /(5) 
    D 

如果我們決定，只有節點A，d和E都需要，我們認識到，以最小的成本的路徑不一定是一個具有最少鏈接。以A - B - D和A - C - E的成本爲7，但A - C - D和C - E的成本爲8.

Answer 1

您想要查找的是離散的Steiner tree。當圖中並非所有頂點都是強制性的，但樹可以在可選頂點處分裂時，問題就是NP難題。

這個問題的維基百科認爲（鏈接在上面）：據信任意好的近似比一般不能在多項式時間內實現。有一個多項式時間算法，找到最小斯坦納樹的一個因子1.39近似值。