u,
w)，在新图中建立边(i,
new,
w-in[u])的边 。 为什么入边的权要减去in[u]，这个后面会解释，在这里先给出算法的步骤 。 然后可以证明，新图中最小树形图的权加上旧图中被收缩
的那个环的权和，就是原图中最小树形图的权 。
上面结论也不做证明了 。 现在依据上面的结论，说明一下为什么出边的权不变，入边的权要减去in
[u] 。 对于新图中的最小树形图T，设指向人工节点的边为e 。 将人工节点展开以后，e指向了一个环 。 假设原先e是指向u的，这个时候我们将环上指向u的边
in[u]删除，这样就得到了原图中的一个树形图 。 我们会发现，如果新图中e的权w'(e)是原图中e的权w(e)减去in[u]权的话，那么在我们删除
掉in[u]，并且将e恢复为原图状态的时候，这个树形图的权仍然是新图树形图的权加环的权，而这个权值正是最小树形图的权值 。 所以在展开节点之后，我们
得到的仍然是最小树形图 。 逐步展开所有的人工节点，就会得到初始图的最小树形图了 。
如果实现得很聪明的话，可以达到找最小入边O(E)，找环
O(V)，收缩O(E)，其中在找环O(V)这里需要一点技巧 。 这样每次收缩的复杂度是O(E)，然后最多会收缩几次呢？由于我们一开始已经拿掉了所有的
自环，我门可以知道每个环至少包含2个点，收缩成1个点之后，总点数减少了至少1 。 当整个图收缩到只有1个点的时候，最小树形图就不不用求了 。 所以我们最
多只会进行V-1次的收缩，所以总得复杂度自然是O(VE)了 。 由此可见，如果一开始不除去自环的话，理论复杂度会和自环的数目有关 。
推荐阅读
- 池塘怎么画，池塘图画大全
- 100米规则 100米简介
- 桃树怎么画，古风桃花树的画法
- 引体向上技巧有哪些 引体向上的好处有哪些
- 雨伞怎么画，荷叶伞怎么画图片
- 引体向上注意事项 引体向上简介
- 钢琴怎么画，钢琴的画法图片
- 蛙跳的动作要领 蛙跳简介
- 时序图怎么画，uml时序图怎么画步骤
- 垒球和棒球的区别 垒球的动作要领