《算法竞赛进阶指南》0x21 树与图的遍历
本章节开始的所有图和树，如果没有额外声明，都是采用邻接表存储的，点的下标为
，无向边存储以两条有向边等价存储
树与图的深度优先遍历
树的深度优先遍历
深度优先遍历，就是在每个点
上面对多条分支时，任意选一条边走下去，执行递归，直到回溯到点
后，再考虑走向其他边
void dfs(int x)
{
v[x] = 1; //记录点 x 被访问过， v 是 visit 的缩写
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (v[y]) continue; //点 y 已经被访问过
dfs(y);
}
}
这段代码访问每个点和每条边
次，其时间复杂度为
，其中
为点数，
为边数
以该段代码作为框架，我们可以统计许多关于树和图的信息
图的连通块划分
树的深度优先遍历，每从
开始一次遍历，就会访问
能够到达的所有点和边
因此通过多次深度优先遍历，可以划分出一张无向图中的各个连通分块
同理对一个森林进行深度优先遍历，可以划分出森林的每一棵树
void dfs(int x)
{
v[x] = cnt;
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (v[y]) continue;
dfs(y);
}
}
// main 函数下
for (int i = 1; i <= n; i ++ )
{
if (!v[i])
{
cnt ++ ;
dfs(i);
}
}
树的 DFS 序
时间戳
按照上述深度优先遍历的过程，以每个节点第一次被访问（v[x] 被赋值为 1 时）的顺序
依次给这
个点
的整数标记，该标记就被称为 时间戳，记为
树的 DFS 序
一般来讲，对树进行深度优先遍历时，对于每个结点，在 刚进入递归后 和 即将回溯前 各记录一次该点的编号
最后产生的长度为
的结点序列就称为 树的 DFS 序
void dfs(int x)
{
a[ ++ m] = x; // a数组存储DFS序
v[x] = 1; // 记录点x被访问过
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (v[y]) continue;
dfs(v[y]);
}
a[ ++ m] = x;
}
DFS 序 的特点是：每个节点
的编号在序列中恰好出现两次
设这两次出现的位置为
和
，则闭区间
就是以
为根的子树的 DFS 序
这样做，使得我们在很多与树相关的问题中，可以通过 DFS 序把子树统计转化为序列上的区间统计
这也是树链剖分的基本思想：将树上路径问题，剖分为多个线段来维护，不过树剖的 dfs 序是要求是重轻儿子 dfs 序
此外，二叉树的先序、中序和后序遍历，也是通过深度优先遍历产生的，由于很简单，就不具体展开了
树的深度
树中各个结点的深度是一种 自顶向下 的统计信息，起初已知根节点的深度为 0
若结点
的深度为
，则他的子节点
的深度为
在深度优先遍历的过程中，结合自顶向下的递推，就可以求出每个结点的深度
请读者列举还有哪些信息一般是 自顶向下 进行统计的
void dfs(int x)
{
v[x] = 1;
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[x];
if (v[y]) continue;
d[y] = d[x] + 1; // 总父节点 x 到子节点 y 递推，计算深度
dfs(y);
}
}
树的重心
也有许多信息是 自底向上 进行统计的，比如以每个结点
为根的子树大小
：
对于叶子结点，我们已知 “以它为根的子树” 大小为
若结点
有
个子节点
，并且以
为根的子树大小分别是
则以
为根节点的子树大小就是
请读者列举还有哪些信息一般是 自底向上 进行统计的
对于一个结点
，如果我们把它从树中删除，那么原来的一棵树可能分成若干个不相连的部分，其中每一部分都是一棵子树
设
表示在删除结点
后产生的子树中，最大的一棵的大小
使
函数取到最小值的结点
就称为整棵树的 重心
通过如下代码，可以求出树的重心：
void dfs(int x)
{
v[x] = size[x] = 1; // 子树 x 的大小
int max_part = 0; //删掉 x 后分成的最大子树的大小
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (v[y]) continue;
dfs(v[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 记录了重心
}
}
树与图的广度优先遍历，拓扑排序
树与图的广度优先遍历需要使用一个队列来实现，起初队列中仅包含一个起点
在广度优先遍历中，不断从队头取出一个结点
，对于
面对多条分支，把沿着每条分支到达的下一个结点（如果未被访问过）插入队尾
重复执行上述过程，直到队列为空
void bfs()
{
memset(d, 0, sizeof(d));
queue<int> q;
q.push(1); d[1] = 1;
while (q.size())
{
int x = q.front(); q.pop();
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if (d[y]) continue;
d[y] = d[x] + 1;
q.push(y);
}
}
}
其中，
为点
在树中的深度，也可以在图中的层次（从起点
走到点
需要经过的点数）
广度优先遍历是一种按照层次顺序进行访问的，它具有如下两个重要性质：
- 在访问完所有的第
层结点后，才会开始访问第
层结点
- 任意时刻，队列中至多有两个层次的结点，即 广度优先遍历队列中的元素，关于层次满足 “二段性” 和 “单调性”
该性质会在后续章节 0x26 “广搜变形” 中再次提及并探讨
广度优先遍历的时间复杂度和深度优先遍历一样，为
拓扑排序
给定一个有向无环图DAG，若一个图中所有点构成的序列
满足：对于图中的每条边
，
在
中都出现在
之前，则称
是该有向无环图顶点的一个 拓扑序，求解序列
的过程就称为 拓扑排序
拓扑排序的思想：不断选择图中入度为
的结点
，然后把
连向的点的入度减
于是可以结合广度优先遍历的框架来高效的实现这个过程：
- 建立空的拓扑序列
- 预处理出所有点的入度
，起初把所有入度为
的点入队
- 取出队头结点
，把
加入拓扑序列
的末尾
- 对于从
出发的每条边
，把
减
，若被减为
，则把
入队
- 重复第 3 ~ 4 步，直到队列为空，此时
即为所求
拓扑排序可以检测 “一个有向图是否有环”：对任意有向图执行上述拓扑排序，完成后检查
序列的长度，若长度小于图中点的数量，则说明某些节点未被遍历，进而说明图中存在环
void add(int x, int y)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
deg[y] ++ ;
}
void topsort()
{
queue<int> q;
for (int i = 1; i <= n; i ++ )
if (!deg[i])
q.push(i);
while (q.size())
{
int x = q.front(); q.pop();
a[ ++ cnt] = x;
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if ( -- deg(y) == 0)
{
q.push(y);
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
int x, y;
cin >> x >> y;
add(x, y);
}
topsort();
for (int i = 1; i <= n; i ++ )
cout << a[i] << " ";
return 0;
}
习题
可达性统计
题目描述
给定一张
个点
条边的有向无环图，分别统计从每个点出发能够到达的点的数量。
输入格式
第一行两个整数
，接下来
行每行两个整数
，表示从
到
的一条有向边。
输出格式
输出共
行，表示每个点能够到达的点的数量。
数据范围
输入样例：
10 10
3 8
2 3
2 5
5 9
5 9
2 3
3 9
4 8
2 10
4 9
输出样例：
1
6
3
3
2
1
1
1
1
1
解析
如果这是一棵树，则每个结点有且仅有一个前驱父节点，因此对于一个结点的两棵子树，他们的子节点不可能有交集。于是可以直接用
表示当前子树中的节点个数，进行统计。 但是本题研究对象是有向无环图，可能存在某个结点的前驱有多种情况，于是上述方法不能使用，因此考虑用状态来表示结点可达的集合
设从点
能到达的点构成的结合为
，则有递推式：
从
出发能够到达的结点，是从
的所有后继结点
出发能够到达的点的并集，再加上
自身
所有在计算所有后继结点的
值之后，就可以计算出该点的
值
这启发我们用拓扑排序算法求出一个拓扑序，然后按照拓扑序的逆序进行计算（因为在拓扑序中，对任意一条边
，
都排在
之前）
关于状态存储，由于至多有
个点要存储，即
个二进制位，而一个 unsigned int 有
位
因此一个点的状态需要
个 unsigned int 来存储，即设计数组 f[N][N / 32 - 1] 来存储状态
为了方便统计，考虑用 STL 的 bitset 来实现这
个二进制位的存储
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
deg[b] ++ ;
}
void topsort()
{
int hh = 1, tt = 0;
for (int i = 1; i <= n; i ++ )
if (!deg[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int x = q[hh ++ ];
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
if ( -- deg[y] == 0)
q[ ++ tt] = y;
}
}
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
topsort();
for (int i = n; i; i -- )
{
int x = q[i];
f[x][x] = 1;
for (int i = h[x]; ~i; i = ne[i])
{
int y = e[i];
f[x] |= f[y];
}
}
for (int i = 1; i <= n; i ++ ) printf("%d\n", f[i].count());
return 0;
}
腾讯云开发者
