C语言树的最大高度问题：寻找最佳根节点

C语言实现树的最大高度问题：寻找最佳根节点

问题描述

在图论中，树是任意两个顶点间有且只有一条路径的图。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。

有一个根的树叫做有根树。

有根树中的节点可以根据到根的距离分层。一棵有根数的层数叫做这棵树的高度。

我们知道，只要确定树根，就可以构造出一棵树。

选取不同的结点当作树根可以构造不同树高的树，你的任务就是选取编号最小的结点，使得以该结点为树根的树的高度最大。

输入

输入数据的第一行为一个整数N (2<=N<=100,000)，表示树的结点数量，结点编号分别为1，2，3，…，N。之后有N-1行，每行有两个整数A和B，表示A结点和B结点之间有一条边。输入数据保证可以构造出一棵有根树。

有多组测试数据，输入以EOF结束。

输出

输出两个整数minNode和Hight，表示以编号minNode为树根的树的最大高度为Hight，如果存在多种情况使得高度Hight最大，输出编号最小的minNode。

样例输入

样例输出

6 5

提示内容：解题思路：

任选一个节点为根节点，进行深度优先搜索，找到与该根节点距离最远的节点。
然后以该节点为根节点，再进行一次深度优先搜索，找到与该节点距离最远的节点。
这个节点就是最终的答案，它到根节点的距离就是树的高度。

**注意：**在深度优先搜索的过程中，需要记录每个节点的父节点，以便换根操作时能够快速更新它的子节点。

代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100005

int n, minNode, Hight;
int father[MAXN], depth[MAXN];
int head[MAXN], to[MAXN * 2], next[MAXN * 2], tot;

void addEdge(int u, int v) {
    to[++tot] = v;
    next[tot] = head[u];
    head[u] = tot;
}

void dfs(int u, int fa) {
    father[u] = fa;
    for (int i = head[u]; i; i = next[i]) {
        int v = to[i];
        if (v != fa) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}

void findMaxDepth(int u) {
    depth[u] = 0;
    dfs(u, 0);
    int maxDepth = 0, maxNode = 0;
    for (int i = 1; i <= n; i++) {
        if (depth[i] > maxDepth) {
            maxDepth = depth[i];
            maxNode = i;
        }
    }
    depth[maxNode] = 0;
    dfs(maxNode, 0);
    for (int i = 1; i <= n; i++) {
        if (depth[i] > Hight) {
            Hight = depth[i];
            minNode = i;
        } else if (depth[i] == Hight && i < minNode) {
            minNode = i;
        }
    }
}

int main() {
    while (scanf("%d", &n) != EOF) {
        tot = 0;
        for (int i = 1; i <= n; i++) {
            head[i] = 0;
        }
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }
        minNode = 1; // 初始化minNode为1
        Hight = 0;
        findMaxDepth(1); // 从节点1开始进行深度优先搜索
        printf("%d %d\n", minNode, Hight);
    }
    return 0;
}

代码解析

结构体定义
- father[MAXN]：记录每个节点的父节点，方便换根操作。
- depth[MAXN]：记录每个节点到根节点的距离，即深度。
- head[MAXN]：存储每个节点的邻接表头指针。
- to[MAXN * 2]：存储边连接的节点编号。
- next[MAXN * 2]：存储邻接表中的下一条边指针。
- tot：记录边的数量。
addEdge函数
- 用于向邻接表中添加边。
dfs函数
- 进行深度优先搜索，更新每个节点的父节点和深度。
findMaxDepth函数
- 输入参数为一个节点，该节点作为当前树的根节点。
- 首先，对该节点进行深度优先搜索，找到距离根节点最远的节点。
- 然后，以该最远节点为新的根节点，再次进行深度优先搜索，找到距离新根节点最远的节点，该节点就是最终的答案。
- 在深度优先搜索的过程中，更新Hight和minNode的值，记录树的最大高度和对应根节点的编号。
main函数
- 循环读取输入数据。
- 初始化邻接表和变量。
- 调用findMaxDepth函数，进行深度优先搜索。
- 输出结果。

注意：

本代码中使用邻接表存储图的结构，可以有效地实现深度优先搜索。
代码中使用father数组记录每个节点的父节点，方便在换根操作时更新子节点的深度。
代码中使用depth数组记录每个节点到根节点的距离，方便计算树的高度。
代码中使用minNode和Hight变量记录树的最大高度和对应根节点的编号，并在深度优先搜索的过程中更新它们的值。
代码中使用if条件语句判断多个根节点对应树高度相同的情况，选择编号最小的根节点作为最终的答案。