《算法导论》教导我们,图有两种表达方法:邻接链表和邻接矩阵。至少是对于有环的图来说,的确是这样。对于树和图究竟怎样表达最好,我一直都在摸索之中。以前在写与图有关的算法的时候,总是要把整个邻接链表(通常是一个很大的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]就可以在读取的时候把所有子结点标注出来。

留言