一种树的表达法
《算法导论》教导我们,图有两种表达方法:邻接链表和邻接矩阵。至少是对于有环的图来说,的确是这样。对于树和图究竟怎样表达最好,我一直都在摸索之中。以前在写与图有关的算法的时候,总是要把整个邻接链表(通常是一个很大的std::vector<std::list<T>>&
)当作参数的一部分送进去。这样看着就很别扭,但是这确实是严格按照《算法导论》的定义实现的。
因此我对我的代码质量深表担忧。但是幸运的是,最近我开始学习起别人的代码,从中获得了一些启示。今天总结的是这么一种特殊的图————自由树的表达方法。这种方法高效,无论是从时间上还是空间上。
假定现在给出一系列树边,每行一条树边记录,由两个数组成。第一个数代表父结点,第二个数代表子结点。这一系列树边可以组成一棵树(或一片森林)。对于这样的信息,利用下面这种方法可以给出高效的表达。
首先我们定义如下结构和数组:
1 | typedef struct{ |
我们知道,在一棵结点数为V的树中,一共有V-1条边。因此给结点和边各开V大小的数组是没问题的。利用这样的数据结构,我们使用如下方法读取边:
1 | //for each edge (u,v) |
从这段代码中,我们可以看出如下基本事实:
- edges以边序号为索引,其中v记录的是该边的子结点,prev记录的是另一条边序号;
- head以结点序号为索引,其中记录的是边序号;
- 在第一次涉及到父结点u时,head[u]为0,此时将此值赋给prev,代表空边。在这之后,head[u]被赋予本边序号;
- 如果再次遇到父结点u,head[u]会被新的边序号覆盖。
- 因此,head实际上存储着以某个结点为父结点时,其在读取顺序中的最后一条边。如果无子结点,则为0.
那么,每个结点最多只存储一条边,如何实现多个子结点的情况?事实上,我们在读到这“最后一条边”时,依照读取顺序的上一条边已经被存储在edges[i].prev中了。按照如下代码,可以方便地完成对某个结点所有子结点的遍历:
1 | for(int k=head[i]; k!=0; k=edges[k].prev){ |
这种方法适用于:
- 数据以自由树形式表达;
- 输入数据是边的信息,且标明了父亲孩子关系。
- 输入边的顺序可以任意。如果要确定根结点,只要再加上一个
bool isroot[V]
就可以在读取的时候把所有子结点标注出来。