擅长:python、mysql、java
<p>我不知道这是不是<strong>解决方案,但这是<strong>解决方案(我想说,这是蛮力的图形版本):</p>
<ol>
<li>使用kruskal或prim算法查找图的MST。这应该是O(E log V)。</li>
<li>生成所有生成树。这可以在<code>O(Elog(V) + V + n) for n = number of spanning trees</code>中完成,据我从2分钟的google了解,这可能会得到改进。</li>
<li>按树的权重等于MST的权重筛选步骤2中生成的列表。这应该是n的O(n)作为步骤2中生成的树的数量。</li>
</ol>
<p>注意:懒洋洋的!生成所有可能的树,然后过滤结果将占用O(V^2)内存,多项式空间要求是有害的-生成树,检查其权重,如果是MST,将其添加到结果列表中,如果不是-丢弃它。<br/>
总时间复杂度:<code>O(Elog(V) + V + n) for G(V,E) with n spanning trees</code></p>