Floyd算法详解：计算二叉树的深度、宽度及节点间距离

Floyd算法详解：计算二叉树的深度、宽度及节点间距离

引用

CSDN

1.

https://m.blog.csdn.net/2301_79868199/article/details/139327141

Floyd算法是一种用于计算图中任意两点间最短路径的经典算法。本文通过一个具体的二叉树问题，详细介绍了Floyd算法的实现过程和应用场景，对于理解算法原理和实际应用都有很大的帮助。

[JLOI2009] 二叉树问题

题目描述

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：

• 深度：4 44
• 宽度：4 44
• 结点 8 和 6 之间的距离：8 88
• 结点 7 和 6 之间的距离：3 33

其中宽度表示二叉树上同一层最多的结点个数，节点u , v u, vu,v之间的距离表示从u uu到v vv的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。

给定一颗以 1 号结点为根的二叉树，请求出其深度、宽度和两个指定节点x , y x, yx,y之间的距离。

输入格式

第一行是一个整数，表示树的结点个数n nn。
接下来n − 1 n - 1n−1行，每行两个整数u , v u, vu,v，表示树上存在一条连接u , v u, vu,v的边。
最后一行有两个整数x , y x, yx,y，表示求x , y x, yx,y之间的距离。

输出格式

输出三行，每行一个整数，依次表示二叉树的深度、宽度和x , y x, yx,y之间的距离。

样例 #1

样例输入 #1

10                                
1 2                            
1 3                            
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6  

�ample输出 #1

4
4
8  

提示

对于全部的测试点，保证1 ≤ u , v , x , y ≤ n ≤ 100 1 \leq u, v, x, y \leq n \leq 1001≤u,v,x,y≤n≤100，且给出的是一棵树。

解题思路

求树的深度，就是求节点到根节点的距离最大值。
求树的宽度，就是求同一深度节点（到根节点距离相同）的数量最大值。

Floyd算法

计算任意两点的最短路径

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            graph[i][j] = MIN(graph[i][j], graph[i][k]+graph[k][j]);
        }
    }
}  

计算通过k处，i节点到j节点的最短距离

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAX(a, b) ((a)<(b)?(b):(a))
#define MIN(a, b) ((a)<(b)?(a):(b))
int n;
int graph[100][100];
int main() {
    cin >> n;
    int u, v;
    memset(graph, 0, sizeof(graph));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j) graph[i][j] = INT_MAX/2;
        }
    }
    for (int i = 0; i < n-1; i++) {
        cin >> u >> v;
        graph[u][v] = 1;
        graph[v][u] = 2;
    }
    cin >> u >> v;
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                graph[i][j] = MIN(graph[i][j], graph[i][k]+graph[k][j]);
            }
        }
    }
    int depth = 0, width = 0, max = 0;
    int d[100] = {0};
    for (int i = 2; i <= n; i++) {
        depth = MAX(graph[1][i], depth);  // 枚举到根节点的深度
        d[graph[1][i]]++;  // 不同深度计数
    }
    for (int i = 1; i <= depth; i++) {
        width = MAX(d[i], width);  // 遍历不同深度的节点数量，计算最大值
    }
    cout << depth+1 << endl;  // 根节点深度为1
    cout << width << endl;
    cout << graph[u][v] << endl;
}