气死我了,最近学习关于最小树形图的问题,无论是CSDN还是博客园,真就是天下文章一大抄,图都用一模一样的,又复杂又高糊,我只是想搞懂存在环,这个环是怎么收缩的,结果给我看了屎一样图和文字表达。一气之下,写一个短文好还描述一下环是怎么收缩成点的。
本文只简述环的收缩
首先,要知道在有向图中,我们把有向图的最小生成树称作最小树形图。
先看文字解释吧:
- 若有向图中有环,那么把这个环看成一个点,对于环内的边我们暂时忽略。
- 既然有环,那就是有回路,也就是环内每个点都有指向该点的边。
- 环外也有指向该环(或者说是收缩成了点)的边,如果没有指向该环的边,就不能构成最小树形图。
- 现在将环展看,关注环内的点。假设环内存在点
V
V
V,对于
V
V
V,一定在环内存在指向它的一条边
E
1
E_1
E1。假设现在环外也存在指向它的一条边
E
2
E_2
E2,那么我们将
E
2
E_2
E2进行更新。更新规则是:
E
2
=
E
2
−
E
1
E_2 = E_2-E_1
E2=E2−E1
看图:
B、C构成环,节点B的入度为2,其中A-->B = 10
,C-->B = 5
,所以更新A-->B = 10-5 = 5
;同理,更新A-->C = 7 - 3 = 4
。
- 有一个问题:如果
A-->B < C-->B
的话,那么减出来不就为负值了么?朱刘算法能解决负值么?
能提出这个问题的同学,就是压根没理解朱刘算法。要知道我们判断环的条件是什么?不只是判断有没有回路,更重要的是,在这之前我们选取的边是最短入度边。就是说B的最短入度边是C传来的,C的最短入度边是B传来的,因此BC才能成环。所以其他点到B的权重一定大于C到B的权重。