1
我想知道是否存在算法在給定所有這些根頂點之間的一組根頂點的情況下計算有向圖中的最小生成樹(最佳分支)但不是圖中的一個根頂點和所有其他頂點。具有多個根頂點的圖中的最小生成樹
給定一組頂點根[1,4,6]和喜歡的一個,如下圖圖G:
...的algorighm應該返回類似綠子在同一張照片上。
我想得到這樣一個MST,它連接提供給算法的所有根頂點。我傾向於認爲,將要成爲算法的結果是包含從G.
所有根頂點和一些其他頂點說明圖G的子圖:
- 我知道,有對有向圖不是MST,但有Chu–Liu/Edmonds algorithm。
- 我想這樣一個算法的結果(如果它實際上是可能的話)將返回一個最佳分支,其中包括圖的頂點和所有根頂點。