0x21 树与图的遍历

树与图最常见的存储方式就是使用一个邻接表保存它们的边集。除非特殊声明，本书在接下来的各章节中默认，给定 $N$ 个点的树或图时，其节点编号均为 $1 \sim N$ ，无向图中的边看作成对出现的双向边，树看作一张具有 $N - 1$ 条边的无向图，它们的边都存储在一个邻接表中，邻接表以 head 数组为表头，使用 ver 和 edge 数组分别存储边的终点和权值，使用 next 数组模拟链表指针（就像我们在 0x13 节中讲解邻接表时所给出的代码那样）。

树与图的深度优先遍历，树的DFS序、深度和重心

深度优先遍历，就是在每个点 $x$ 上面对多条分支时，任意选一条边走下去，执行递归，直至回溯到点 $x$ 后，再考虑走向其他的边，如右图所示。根据上面提到的存储方式，我们可以采用下面的代码，调用dfs(1)，对一张图进行深度优先遍历。

void dfs(int x) {  
    v[x] = 1; // 记录点  $x$  被访问过， $v$  是 visit 的缩写  
    for (int i = head[x]; i; i = next[i]) {  
        int y = ver[i];  
        if (v[y]) continue; // 点  $y$  已经被访问过了  
            dfs(y);  
    }  
}

这段代码访问每个点和每条边恰好1次（如果是无向边，正反向各访问1次），其时间复杂度为 $O(N + M)$ ，其中 $M$ 为边数。以这段代码为框架，我们可以统计许多关于树和图的基本信息。

时间戳

按照上述深度优先遍历的过程，按照每个节点第一次被访问 $(v[x]$ 被赋值为1时）的顺序，依次给予这 $N$ 个节点 $1\sim N$ 的整数标记，这个标记就被称为时间戳，记为 $dfn_{\circ}$

例如，在本页的图中， $dfn[1] = 1$ ， $dfn[2] = 2$ ， $dfn[8] = 3$ ， $dfn[5] = 4$ ， $dfn[7] = 5$ ， $dfn[4] = 6$ ， $dfn[3] = 7$ ， $dfn[9] = 8$ ， $dfn[6] = 9$ 。

树的DFS序

一般来讲，我们在对树进行深度优先遍历时，对于每个节点，在刚进入递归后以及即将回溯前各记录一次该点的编号，最后产生的长度为 $2N$ 的节点序列就称为树的DFS序。

void dfs(int x) {
    a[++m] = x; // a数组存储 DFS 序
    v[x] = 1; // 记录点 x 被访问过
    for (int i = head[x]; i; i = next[i]) {
        int y = ver[i];
        if (v[y]) continue;
        dfs(y);
    }
    a[++m] = x;
}

DFS 序的特点是：每个节点 $x$ 的编号在序列中恰好出现两次。设这两次出现的位置为 $L[x]$ 与 $R[x]$ ，那么闭区间 $[L[x], R[x]]$ 就是以 $x$ 为根的子树的 DFS 序。这使我们在很多与树相关的问题中，可以通过 DFS 序把子树统计转化为序列上的区间统计。我们在后续的章节中会涉及此类题目。

DFS序：1,2,8,8,5,5,2,7,7,4,3,9,9,3,6,6,4,1

子树2 子树7 子树4

另外，二叉树的先序、中序与后序遍历序列，也是通过深度优先遍历产生的，大多数程序设计入门级的书籍上都有详细讲解，在此就不再赘述。读者应该掌握这几种遍历，以及它们之间的联系和转化。

树的深度

树中各个节点的深度是一种自顶向下的统计信息。起初，我们已知根节点的深度为0。若节点 $x$ 的深度为 $d[x]$ ，则它的子节点 $y$ 的深度就是 $d[y] = d[x] + 1$ 。在深度优先遍历的过程中结合自顶向下的递推，就可以求出每个节点的深度 $d$ 。请读者尝试列举还有哪些信息一般是自顶向下进行统计的。

void dfs(int x) {

$\begin{array}{l}\mathrm{v}[\mathrm{x}] = 1;\\ \mathrm{for~(int~i = ~head[x];~i;~i = ~next[i])~\{}\\ \mathrm{int~y = ~ver[i];}\\ \mathrm{if~(v[y])~continue;}\\ \mathrm{d[y] = d[x] + 1;~//~from~父~节点~x~到~子~节点~y~递推,~计算~深度}\\ \mathrm{dfs(y);}\\ \}}\\ \}} \end{array}$

树的重心

当然，也有许多信息是自底向上进行统计的，比如以每个节点 $x$ 为根的子树大小 $size[x]$ 。对于叶子节点，我们已知“以它为根的子树”大小为1。若节点 $x$ 有 $k$ 个子节点 $y_1 \sim y_k$ ，并且以 $y_1 \sim y_k$ 为根的子树大小分别是 $size[y_1], size[y_2], \dots, size[y_k]$ ，则以 $x$ 为根的子树的大小就是 $size[x] = size[y_1] + size[y_2] + \dots + size[y_k] + 1$ 。请读者尝试列举还有哪些信息一般是自底向上进行统计的。

对于一个节点 $x$ ，如果我们把它从树中删除，那么原来的一棵树可能会分成若干个不相连的部分，其中每一部分都是一棵子树。设 max_part(x) 表示在删除节点 $x$ 后产生的子树中，最大的一棵的大小。使 max_part 函数取到最小值的节点 $p$ 就称为整棵树的重心。例如上图中的树的重心应该是节点 1。通过下面的代码，我们可以统计出 size 数组，并求出树的重心。

void dfs(int x) {  
    v[x] = 1; size[x] = 1; // 子树  $x$  的大小  
    int max_part = 0; // 删掉  $x$  后分成的最大子树的大小  
    for (int i = head[x]; i; i = next[i]) {  
        int y = ver[i];  
    if (v[y]) continue; // 点  $y$  已经被访问过了

dfs(y); size[x] += size[y]; //从子节点向父节点递推 max_part = max(max_part, size[y]); } max_part = max(max_part, n - size[x]); //n为整棵树的节点数目 if (max_part < ans) { ans = max_part; //全局变量ans记录重心对应的max_part值 pos = x; //全局变量pos记录了重心 }

图的连通块划分

上面的代码每从 $x$ 开始一次遍历，就会访问 $x$ 能够到达的所有的点与边。因此，通过多次深度优先遍历，可以划分出一张无向图中的各个连通块①。同理，对一个森林进行深度优先遍历，可以划分出森林中的每棵树。如下面的代码所示，cnt 就是无向图包含的连通块的个数， $v$ 数组标记了每个点属于哪一个连通块。

void dfs(int x) {  
    v[x] = cnt;  
    for (int i = head[x]; i; i = next[i]) {  
        int y = ver[i];  
        if (v[y]) continue;  
        dfs(y);  
    }  
}  
for (int i = 1; i <= n; i++) // 在 int main() 中  
    if (!v[i]) {  
        cnt++;  
        dfs(i);  
    }

树与图的广度优先遍历，拓扑排序

树与图的广度优先遍历需要使用一个队列来实现。起初，队列中仅包含一个起点（例如1号节点）。在广度优先遍历的过程中，我们不断从队头取出一个节点 $x$ ，对于

$x$ 面对的多条分支，把沿着每条分支到达的下一个节点（如果尚未访问过）插入队尾。重复执行上述过程直到队列为空。

我们可以采用下面的代码对一张图进行广度优先遍历（关于代码中的 STL queue, 参见 0x71 节）。

void bfs(){ memset(d,0,sizeof(d)); queue<int>q; q.push(1);d[1] = 1; while (q.size() > 0){ int  $\mathbf{x} =$  q.front();q.pop(); for (int i = head[x]; i; i = next[i]) { int y  $=$  ver[i]; if (d[y]) continue; d[y]  $=$  d[x] + 1; q.push(y); } }

在上面的代码中，我们在广度优先遍历的过程中顺便求出了一个 $d$ 数组。对于一棵树来讲， $d[x]$ 就是点 $x$ 在树中的深度。对于一张图来讲， $d[x]$ 被称为点 $x$ 的层次（从起点1走到点 $x$ 需要经过的最少点数）。从代码和示意图中我们可以发现，广度优先遍历是一种按照层次顺序进行访问的方法，它具有如下两个重要性质：

在访问完所有的第 $i$ 层节点后，才会开始访问第 $i + 1$ 层节点。
任意时刻，队列中至多有两个层次的节点。若其中一部分节点属于第 $i$ 层，则另一部分节点属于第 $i + 1$ 层，并且所有第 $i$ 层节点排在第 $i + 1$ 层节点之前。也就是说，广度优先遍历队列中的元素关于层次满足“两段性”和“单调性”。

这两条性质是所有广度优先思想的基础，请读者务必牢记，我们在0x26节的“广搜变形”中会再次提及并探讨。与深度优先遍历一样，上面这段代码的时间复杂度也是 $O(N + M)$ 。

拓扑排序

给定一张有向无环图①，若一个由图中所有点构成的序列 $A$ 满足：对于图中的每条边 $(x, y)$ ， $x$ 在 $A$ 中都出现在 $y$ 之前，则称 $A$ 是该有向无环图顶点的一个拓扑序。求解序列 $A$ 的过程就称为拓扑排序。

拓扑排序过程的思想非常简单，我们只需要不断选择图中入度为0的节点 $x$ ，然后把 $x$ 连向的点的入度减1。我们可以结合广度优先遍历的框架来高效地实现这个过程：

建立空的拓扑序列 $A$ 。
预处理出所有点的入度 $\deg [i]$ ，起初把所有入度为 0 的点入队。
3.取出队头节点 $x$ ，把 $\mathcal{X}$ 加入拓扑序列 $A$ 的末尾。
对于从 $x$ 出发的每条边 $(x, y)$ ，把 $\deg[y]$ 减 1。若被减为 0，则把 $y$ 入队。
重复第 $3 \sim 4$ 步直到队列为空，此时 $A$ 即为所求。

拓扑排序可以判定有向图中是否存在环。我们可以对任意有向图执行上述过程，在完成后检查 $A$ 序列的长度。若 $A$ 序列的长度小于图中点的数量，则说明某些节点未被遍历，进而说明图中存在环。读者可以参考下面的程序，画图模拟拓扑排序算法。

void add(int x, int y) { // 在邻接表中添加一条有向边
    ver[++tot] = y, next[tot] = head[x], head[x] = tot;
    deg[y]++;
}
void topsort() { // 拓扑排序
        queue<int> q;
        for (int i = 1; i <= n; i++) 
            if (deg[i] == 0) q.push(i);
        while (q.size()) {
            int x = q.front(); q.pop();
            a[++cnt] = x;
            for (int i = head[x]; i; i = next[i]) {
                int y = ver[i];
            }
        }
    }
};

if（--deg[y]  $\equiv = 0$  ）q.push(y);   
}   
}   
}   
int main() { cin >> n >> m; //点数、边数 for (int i  $= 1$  ;i  $\Leftarrow$  m;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); } topsort(); for (int i  $= 1$  ;i  $\Leftarrow$  cnt; i++) printf("%d ",a[i]); cout << endl;   
}

【例题】可达性统计

给定一张 $N$ 个点 $M$ 条边的有向无环图，分别统计从每个点出发能够到达的点的数量。 $N, M \leq 30000$ 。

设从点 $x$ 出发能够到达的点构成的集合是 $f(x)$ ，则显然有：

f (x) = \{x \} \cup \left(\bigcup_ {\text {存 在 有 向 边} (x, y)} f (y)\right)

也就是说，从 $x$ 出发能够到达的点，是从“ $x$ 的各个后继节点 $y$ ”出发能够到达的点的并集，再加上点 $x$ 自身。所以，在计算出一个点的所有后继节点的 $f$ 值之后，就可以计算出该点的 $f$ 值。这启发我们先用拓扑排序算法求出一个拓扑序，然后按照拓扑序的倒序进行计算——因为在拓扑序中，对任意的一条边 $(x, y)$ ， $x$ 都排在 $y$ 之前。

回想起在第 $0 \times 01$ 节中学到的状态压缩方法，我们可以使用一个 $N$ 位二进制数存储每个 $f(x)$ ，其中第 $i$ 位是1表示 $x$ 能到 $i$ ，0表示不能到 $i$ 。这样一来，对若干个集合求并，就相当于对若干个 $N$ 位二进制数做“按位或”运算。最后，每个 $f(x)$ 中1的个数就是从 $x$ 出发能够到达的节点数量。

这个 $N$ 位二进制数可以压缩成 $N / 32 + 1$ 个无符号32位整数 unsigned int 进行存储，更简便的方法是直接使用 $\mathrm{C}++$ STL 中为我们提供的 bitset（参见第 0x71 节），bitset 支持我们上述所需的所有运算。该拓扑排序+状态压缩算法花费的时间规模约为

$N(N + M) / 32$ ，所需空间大小约为 $N^2 /8$ 字节。

0x21_树与图的遍历