一种树的表达法

《算法导论》教导我们，图有两种表达方法：邻接链表和邻接矩阵。至少是对于有环的图来说，的确是这样。对于树和图究竟怎样表达最好，我一直都在摸索之中。以前在写与图有关的算法的时候，总是要把整个邻接链表（通常是一个很大的std::vector<std::list<T>>&）当作参数的一部分送进去。这样看着就很别扭，但是这确实是严格按照《算法导论》的定义实现的。

因此我对我的代码质量深表担忧。但是幸运的是，最近我开始学习起别人的代码，从中获得了一些启示。今天总结的是这么一种特殊的图————自由树的表达方法。这种方法高效，无论是从时间上还是空间上。

假定现在给出一系列树边，每行一条树边记录，由两个数组成。第一个数代表父结点，第二个数代表子结点。这一系列树边可以组成一棵树（或一片森林）。对于这样的信息，利用下面这种方法可以给出高效的表达。

首先我们定义如下结构和数组：

1
2
3
4
5
6
7
typedef struct{
    int v;
    int prev;
}edge_t;

edge_t edges[N]; //边
int head[N];     //结点

我们知道，在一棵结点数为V的树中，一共有V-1条边。因此给结点和边各开V大小的数组是没问题的。利用这样的数据结构，我们使用如下方法读取边：

1
2
3
4
//for each edge (u,v)
edges[i].v=v;
edges[i].prev=head[u];
head[u]=i;

从这段代码中，我们可以看出如下基本事实：

  1. edges以边序号为索引，其中v记录的是该边的子结点，prev记录的是另一条边序号；
  2. head以结点序号为索引，其中记录的是边序号；
  3. 在第一次涉及到父结点u时，head[u]为0，此时将此值赋给prev，代表空边。在这之后，head[u]被赋予本边序号；
  4. 如果再次遇到父结点u，head[u]会被新的边序号覆盖。
  5. 因此，head实际上存储着以某个结点为父结点时，其在读取顺序中的最后一条边。如果无子结点，则为0.

那么，每个结点最多只存储一条边，如何实现多个子结点的情况？事实上，我们在读到这“最后一条边”时，依照读取顺序的上一条边已经被存储在edges[i].prev中了。按照如下代码，可以方便地完成对某个结点所有子结点的遍历：

1
2
3
for(int k=head[i]; k!=0; k=edges[k].prev){
    //do something
}

这种方法适用于：

  • 数据以自由树形式表达；
  • 输入数据是边的信息，且标明了父亲孩子关系。
  • 输入边的顺序可以任意。如果要确定根结点，只要再加上一个bool isroot[V]就可以在读取的时候把所有子结点标注出来。

留言

▲