Q

有向加權圖

graph

2013-01-17 68 views 4 likes

4

我尋找以下問題的算法找到最高平均重樹：給定一個定向加權圖G，找一棵樹T在G，使得平均體重T是最大的。有向加權圖

2013-01-17 user1986697

+0

有趣的問題。你能給出關於樹上圖形和約束的假設的更多信息嗎？有沒有什麼能阻止我們採取只有最大重量邊緣和兩個相應節點的樹？ – Khaur

+0

「T」的平均重量是什麼意思？因爲如果你說平均值是（T中邊的權重總和/ T中邊的數量），那麼可以立即說出挑選權重最高的邊。所以請你清楚地說明。 – Reza

A

回答

0

鑑於圖G以升序
排序邊緣（最小重量第一）
削頂邊緣（一個具有最小重量）
剪切孤兒頂點
現在是樹嗎？
- 是：轉到步驟6
- 否：轉到步驟3
返回摹

2013-04-06 06:10:21

相關問題