圆方树的引入
我们知道,图没有很好的性质,而树有很多性质,并且容易通过很多方式来维护树上信息,因此将图上问题转化为树上问题是我们想要解决的。圆方树就是将图转化为树的数据结构。
圆方树的分类
圆方树分为两类:狭义圆方树,广义圆方树。
狭义圆方树
狭义圆方树是可以用来将仙人掌图转化为树的一种数据结构。
广义圆方树
广义圆方树是可以用来将所有无向图转化为树的一种数据结构。
狭义圆方树
作者还没学广义圆方树,所以先来讲狭义圆方树。
仙人掌图
什么是仙人掌图?这里给出定义:
任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。
简单来说,就是图中有环并且图中任意两个环没有公共边的图。
如果你还不懂的话请看下图。
