4

我正在搜索以下问题的算法:给定一个有向加权图G,找到一棵树TG使得 的平均权重T最大。

4

1 回答 1

0
  1. Given a graph G

  2. Sort Edges in an ascending order (minimum weight first)

  3. Cut Top edge (one with smallest weight)

  4. Cut orphan vertices

  5. Is it a tree now ?

    • Yes: go to step 6

    • No: go to step 3

  6. Return G

于 2013-04-06T06:10:21.187 回答