Algorithm14.7 树的图解法
[TOC]
树的图解法
树【不仅限于二叉树，多叉树都没问题的】转化为图【无向图】
- 树的深度：【图中其他所有点】 离 【根节点对应的图中的节点】 距离最远的
- 树的宽度：图中距离 【根节点对应的图中的节点】 各个不同距离中，个数最多的点（例如，距离为1的点有2个，距离为2的点有3个，距离为3的点有1个，所以宽度为3）
- LCA问题：可以通过图论中的最短路来解决=》floyd直接暴力出来
基础转换
https://www.luogu.com.cn/problem/P3884
#include <iostream>
using namespace std;
const int maxn = 105;
const int inf = 1e8+9;
int n, d[maxn][maxn], ta, tb, depth, w[maxn], width = 1, ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (i != j) d[i][j] = inf;
for (int i = 1; i < n; ++i) {
scanf("%d%d", &ta, &tb);
d[ta][tb] = 1; d[tb][ta] = 2;
}
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
scanf("%d%d", &ta, &tb);
for (int i = 1; i <= n; ++i) {
depth = max(depth, d[1][i]);
w[d[1][i]]++;
}
for (int i = 1; i <= depth+1; ++i) width = max(width, w[i]);
printf("%d\n%d\n%d\n", depth+1, width, d[ta][tb]);
return 0;
}