当前位置：首页 > news >正文

DFS的树上应用

news 来源：原创 2024/11/13 10:35:37

一、前言

二、树上的DFS

1、树的重心

2、树的重心例题

3、树的直径

4、树的直径例题

（1）做两次DFS

三、拓扑排序与DFS

1、用DFS解拓扑排序

2、欧拉路与DFS

3、用DFS输出一个欧拉回路

一、前言

本文主要讲了树上的DFS、树的重心、树的直径、拓扑排序与DFS、欧拉路等理论内容。

二、树上的DFS

1、树的重心

树的重心 u：以树上任意一个结点为根计算它的子树的结点数，如果结点 u 的最大的子树的结点数最少，那么 u 就是树的重心。
删除点 u 后得到两棵或更多棵互不连通的子树，其中最大子树的结点数最小。u 是树上最平衡的点。

如何计算以结点 i 为根的子树的结点数量？
对 i 做 DFS：从 i 出发，递归到最底层后返回，每返回一个结点，结点数加 1，直到所有结点都返回，就得到了子树上结点总数。
因为每个结点只返回 1 次，所以这个方法是对的。

那么如何寻找树的重心呢？

暴力法：

删除树上的一个结点 u，得到几个孤立的连通块，可以对每个连通块做一次 DFS，分别计算结点数量。对整棵树逐一删除每个结点，重复上述计算过程，就得到了每个结点的最大连通块。

优化：只需要一次 DFS，就能得到每个结点的最大连通块。

删除 u 得到三个连通块:

（1）包含 1 的连通块; （2）包含 2 的连通块；（3）包含 3 的连通块。

这三个连通块的数量如何计算？

从任意一个点开始 DFS，假设从 1 开始，1 是 u 的父结点。DFS 到结点 u 后，从 u 开始继续 DFS，得到它的子树 2 和 3 的结点数量 (2) 和 (3) ，设 u 为根的子树的结点数量是 d[u]，则 d[u] = (2) + (3) + 1。那么 (1) 的数量等于 n-d[u]，n是结点总数。记录 (1)、(2)、(3) 的最大值，就得到了 u 的最大连通块。

这样通过一次 DFS，每个结点的最大连通块都得到了计算，总复杂度 O(n)。

2、树的重心例题

【问题描述】

城里有一个黑手党组织。把黑手党的人员关系用一棵树来描述，教父是树的根，每个结点是一个黑手党徒。为了保密，每人只和他的父结点和他的子结点联系。警察知道哪些人互相来往，但是不知他们的关系。警察想找出谁是教父。

警察假设教父是一个聪明人：教父懂得制衡手下的权力，所以他直属的几个小头目，每个小头目属下的人数差不多。也就是说，删除根之后，剩下的几个互不连通的子树（连通块)，其中最大的连通块应该尽可能小。帮助警察找到哪些人可能是教父。

【输入】

第一行是 n，表示黑手党的人数，2 <= n <= 50000。黑手党徒的编号是 1 到 n。下面有 n-1 行，每行有 2 个整数，即有联系的 2 个人的编号。

【输出】

输出疑似教父的结点编号，从小到大输出。

【输入样例】

6

1 2

2 3

2 4

4 5

3 6

【输出样例】

2 3

import sys
sys.setrecursionlimit(300000)    #设置递归深度,否则不能通过100%的测试

def dfs(u,fa):
    global num,maxnum   #num:教父的数量
    d[u]=1              #递归到最底层时，结点数加1
    tmp=0
    for v in edges[u]:  #遍历u的子节点
        if v==fa:
            continue
        dfs(v,u)        #递归子节点，计算v这个子树的结点数量
        d[u]+=d[v]      #计算以u为根的节点数量
        tmp=max(tmp,d[v])   #记录u的最大子树的节点数量
    tmp=max(tmp,n-d[u]) #tmp=u 的最大连通块的结点数
        #以上计算出了u的最大连通块
        #下面统计疑似教父。如果一个结点的最大连通块比其他结点的都小，它是疑似教父
    if tmp<maxnum:      #一个疑似教父
        maxnum=tmp      #更新"最小的"最大连通块
        num=1
        ans[1]=u        #把教父记录在第1个位置
    elif tmp==maxnum:
        num+=1
        ans[num]=u      #疑似教父有多个，记录在后面

maxnum=int(1e9)
n=int(input())
d=[0]*(n+1)     #以u为根的子树的结点数量
ans=[0]*(n+1)   #记录教父
num=0           #教父的数量
edges=[[] for i in range(n+1)]      #邻接表
for i in range(n-1):
    a,b=map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)
dfs(1,0)
s=sorted(ans[1:num+1])      #对教父排序
for i in range(num):
    print(s[i],end=' ')     #按顺序打印所有教父

3、树的直径

树的直径是指树上最远的两点间的距离，又称为树的最远点对。

有两种方法求树的直径：

（1）做两次DFS（或BFS）；

（2）树形DP。

复杂度都是 O(n)。

-----------------------------------------------------------------------------------------------

优点和缺点：

（1）做两次DFS（或BFS）

优点：能得到完整的路径。它用搜索的原理，从起点 u 出发一步一步求 u 到其他所有点的距离，能记录路径经过了哪些点。

缺点：不能用于有负权边的树。

（2）树形DP

优点：允许树上有负权边。

缺点：只能求直径的长度，无法得到这条直径的完整路径。

4、树的直径例题

【问题描述】

求树的直径。

【输入描述】

第一行是整数 n，表示树的 n 个点。点的编号从 1 开始。后面 n-1 行，每行 3 个整数 a、b、w，表示点 a、b 之间有一条边，边长为 w。

【输出描述】

一个整数，表示树的直径。

【输入样例】

5

1 2 5

1 3 19

1 4 23

4 5 12

【输出样例】

54

（1）做两次DFS

当边权没有负值时，计算树的直径可以通过做两次 DFS 解决，步骤是：

（1）从树上的任意一个点 r 出发，用 DFS 求距离它最远的点 s。 s 肯定是直径的两个端点之一。（2）从 s 出发，用 DFS 求距离 s 最远的点 t 。t 是直径的另一个端点。

s、t 就是距离最远的两个点，即树的直径的两个端点。

证明：

把这棵树所有的边想象成不同长度的柔性绳子，并假设已经找到了直径的两个端点 s 和 t。
双手抓住 s 和 t，然后水平拉直成一条长线，这是这棵树能拉出来的最长线。
这时，其他的绳子和点会下垂。
任选一个除 s 和 t 以外的点 r，它到 s（或t）的距离肯定是最远的。
如果不是最远的，那么下垂的某个点就能替代s，这跟假设 s 是直径的端点矛盾。

但是这个方法不能用于有负权边的树。例：

第一次 DFS，若从点1出发，得到的最远端点 s 为点 2；
第二次 DFS 从点 2 出发，得 t 为点 4。
但是，实际上这棵树的直径的两个端点应该是 3、4。

总结：以贪心原理进行路径长度搜索的 DFS，当树上有负权边时，只能在局部获得最优，而无法在全局获得最优。

import sys
sys.setrecursionlimit(300000)

def dfs(u,fa,d):        #用dfs计算从u到每个子结点的距离
    dist[u]=d
    for v,w in edges[u]:
        if v!=fa:       #很关键，不回头搜父结点
            dfs(v,u,d+w)

n=int(input())
dist=[0]*(n+1)  #记录距离
edges=[[] for i in range(n+1)]      #邻接表
for i in range(n-1):
    a,b,w=map(int,input().split())
    edges[a].append((b,w))
    edges[b].append((a,w))
dfs(1,-1,0)
s=1
for i in range(1,n+1):      #找最远的结点s，s是直径的一个端点
    if dist[i]>dist[s]:
        s=i
dfs(s,-1,0)         #从s出发，计算以s为起点，到树上每个结点的距离
t=1
for i in range(1,n+1):      #找直径的另一个端点t
    if dist[i]>dist[t]:
        t=i
print(dist[t])      #打印树的直径的长度

三、拓扑排序与DFS

设有 a、b、c、d 等事情，其中 a 有最高优先级，b、c 优先级相同，d 是最低优先级，表示为a → (b,c) → d，那么 abcd 或者 acbd 都是可行的排序。

把事情看成图的点，先后关系看成有向边，问题转化为在图中求一个有先后关系的排序，这就是拓扑排序。

出度：以点 u 为起点的边的数量，称为 u 的出度。
入度：以点 v 为终点的边的数量，称为 v 的入度。
一个点的入度和出度，体现了这个点的先后关系。如果一个点的入度等于 0，说明它是起点，是排在最前面的；如果它的出度等于0，说明它是排在最后面的。
图中，点 a、c 的入度为 0，它们都是优先级最高的事情；d 的出度为 0，它的优先级最低。

1、用DFS解拓扑排序

DFS 天然适合拓扑排序。
DFS 深度搜索的原理，是沿着一条路径一直搜索到最底层，然后逐层回退。
这个过程正好体现了点和点的先后关系，天然符合拓扑排序的原理。

如果只有一个点 u 是 0 入度的，那么从 u 开始 DFS， DFS 递归返回的顺序就是拓扑排序（是一个逆序）。
DFS 递归返回的首先是最底层的点，它一定是 0 出度点，没有后续点，是拓扑排序的最后一个点；然后逐步回退，最后输出的是起点 u；输出的顺序是一个逆序。
从 a 开始，递归返回的顺序见点旁边的划线数字：cdba，是拓扑排序的逆序。

如果有多个入度为 0 的点？
想象有一个虚拟的点 v，它单向连接到所有其他点。这个点就是图中唯一的 0 入度点，图中所有其他的点都是它的下一层递归；而且它不会把原图变成环路。从这个虚拟点开始 DFS，就完成了拓扑排序。
图 (1) 有 2 个 0 入度点 a 和 f
图 (2) 想象有个虚拟点 v，递归返回的顺序见点旁边划线数字，返回的是拓扑排序的逆序。