圆方树的引入
我们知道,图没有很好的性质,而树有很多性质,并且容易通过很多方式来维护树上信息,因此将图上问题转化为树上问题是我们想要解决的。圆方树就是将图转化为树的数据结构。
圆方树的分类
圆方树分为两类:狭义圆方树,广义圆方树。
狭义圆方树
狭义圆方树是可以用来将仙人掌图转化为树的一种数据结构。
广义圆方树
广义圆方树是可以用来将所有无向图转化为树的一种数据结构。
狭义圆方树
作者还没学广义圆方树,所以先来讲狭义圆方树。
仙人掌图
什么是仙人掌图?这里给出定义:
任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。
简单来说,就是图中有环并且图中任意两个环没有公共边的图。
如果你还不懂的话请看下图。
建树
我们回顾 Tarjan 算法。
在无向图中,Tarjan 算法找到图中的环,并且将环缩成一个点,这样就将原来的无向图变成了一棵树。
那这里你可能会问,那我还要圆方树干嘛,有 Tarjan 不就够了吗?还真不行,因为 Tarjan 将环都缩成一个点了,因此原来环上的很多信息你都没有办法保留了,所以在面对很多问题时就用不了了。
但是 Tarjan 算法给我们启发:可以将环看成一个整体。
于是产生了圆方树。
如图,原图中的每一个点看作一个圆点,而每一个环看作一个方点。
这时候我们将原来的边删去,每个圆点与它所在的环对应的方点之间连一条边,这就建好了一棵圆方树。