C语言树直径算法详解（从零开始掌握树的最长路径计算）

什么是树的直径？

树是一种无环连通图。树的直径就是这棵树中距离最远的两个节点之间的边数。例如，下图中红色路径即为该树的直径。

注意：树的直径不一定经过根节点，它可能完全位于某一个子树中。

算法思路

计算树直径的经典方法是两次BFS（广度优先搜索）或DFS（深度优先搜索）：

1. 任选一个起点（比如节点0），找到离它最远的节点A；
2. 再从节点A出发，找到离A最远的节点B；
3. 那么A到B的路径长度就是树的直径。

但更常用且适合递归实现的方法是：通过一次DFS，在回溯过程中记录每个节点向下延伸的最长和次长路径，两者之和即为经过该节点的最长路径。我们将在下面用C语言实现这种方法。

C语言实现树直径算法

我们将使用邻接表表示树，并通过DFS递归计算直径。

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_NODES 10000// 邻接表节点struct Node {    int vertex;    struct Node* next;};// 图结构struct Graph {    int numVertices;    struct Node** adjLists;};// 创建新节点struct Node* createNode(int v) {    struct Node* newNode = malloc(sizeof(struct Node));    newNode->vertex = v;    newNode->next = NULL;    return newNode;}// 创建图struct Graph* createGraph(int vertices) {    struct Graph* graph = malloc(sizeof(struct Graph));    graph->numVertices = vertices;    graph->adjLists = malloc(vertices * sizeof(struct Node*));    for (int i = 0; i < vertices; i++)        graph->adjLists[i] = NULL;    return graph;}// 添加边（无向图）void addEdge(struct Graph* graph, int src, int dest) {    // 添加 dest 到 src 的邻接表    struct Node* newNode = createNode(dest);    newNode->next = graph->adjLists[src];    graph->adjLists[src] = newNode;    // 添加 src 到 dest 的邻接表    newNode = createNode(src);    newNode->next = graph->adjLists[dest];    graph->adjLists[dest] = newNode;}// 全局变量：记录最大直径int diameter = 0;// DFS函数：返回从当前节点向下延伸的最长路径长度int dfs(struct Graph* graph, int u, int parent) {    int firstMax = 0;   // 最长路径    int secondMax = 0;  // 次长路径    struct Node* temp = graph->adjLists[u];    while (temp) {        int v = temp->vertex;        if (v != parent) { // 避免回溯到父节点            int childDepth = dfs(graph, v, u);            if (childDepth > firstMax) {                secondMax = firstMax;                firstMax = childDepth;            } else if (childDepth > secondMax) {                secondMax = childDepth;            }        }        temp = temp->next;    }    // 经过当前节点u的最长路径 = firstMax + secondMax    if (firstMax + secondMax > diameter) {        diameter = firstMax + secondMax;    }    // 返回从u向下延伸的最长路径（+1 表示加上当前边）    return firstMax + 1;}int main() {    int n = 5; // 节点数    struct Graph* graph = createGraph(n);    // 构建一棵树：0-1-2-3 和 1-4    addEdge(graph, 0, 1);    addEdge(graph, 1, 2);    addEdge(graph, 2, 3);    addEdge(graph, 1, 4);    diameter = 0;    dfs(graph, 0, -1); // 从任意节点开始DFS    printf("树的直径为：%d\n", diameter);    return 0;}

代码解析

• dfs 函数返回从当前节点向下能延伸的最长路径长度（边数）。
• 在遍历子节点时，我们维护两个值：firstMax（最长）和 secondMax（次长）。
• 经过当前节点的最长路径 = firstMax + secondMax，我们用全局变量 diameter 记录最大值。
• 最终，diameter 就是整棵树的直径。

以上代码的时间复杂度为 O(n)，其中 n 是节点数量，非常适合处理大规模树结构。

应用场景

C语言图论算法中的树直径问题常用于：

• 网络中最远通信延迟估算
• 分布式系统中任务调度优化
• 二叉树直径求解（可视为本算法的特例）
• 文件系统目录结构分析

总结

通过本教程，你已经掌握了如何用C语言实现树的最长路径计算。核心思想是利用DFS在回溯过程中动态更新最长和次长路径。这种方法简洁高效，是解决C语言树直径算法问题的标准做法。

建议你动手运行上面的代码，修改树的结构，观察直径的变化，加深理解。祝你编程愉快！