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

穿越数据森林与网络迷宫：树与图上动态规划实战指南

news 2025/5/6 10:35:48

在 C++ 算法的浩瀚宇宙中，树与图就像是神秘的迷宫和茂密的森林，充满了未知与挑战。而动态规划则是我们探索其中的神奇罗盘，帮助我们找到最优路径。今天，就让我们一起深入这片神秘领域，揭开树与图上动态规划的神秘面纱！

树与图上动态规划的独特魅力

与线性动态规划相比，树与图上的动态规划更加复杂，因为它们的结构不再是简单的线性，而是具有分支和循环。但正是这种复杂性，让它们能够解决更多现实世界中的问题，比如城市交通网络的最优路线规划、社交网络中的信息传播分析等。在树与图上使用动态规划，就像是在错综复杂的迷宫中，通过标记一个个关键点（状态），找到从起点到终点的最佳路径（最优解）。

树结构上的动态规划

树结构天然具有递归和层次的特性，这使得树的动态规划通常从叶子节点向根节点进行状态转移。我们以 “树的最大路径和” 问题为例来深入理解。

问题描述

给定一棵二叉树，找到从树中某个节点到其他节点的路径中，节点值之和最大的路径。路径可以从任意节点开始，到任意节点结束。

代码示例

#include <iostream>
#include <algorithm>
using namespace std;// 定义二叉树节点结构
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};int maxPathSum(TreeNode* root, int& maxSum) {if (root == nullptr) {return 0;}// 递归计算左子树的最大贡献值int leftMax = max(0, maxPathSum(root->left, maxSum));// 递归计算右子树的最大贡献值int rightMax = max(0, maxPathSum(root->right, maxSum));// 计算经过当前节点的路径和int currentPathSum = root->val + leftMax + rightMax;// 更新全局最大路径和maxSum = max(maxSum, currentPathSum);// 返回当前节点能为父节点提供的最大贡献值return root->val + max(leftMax, rightMax);
}int maxPathSum(TreeNode* root) {int maxSum = INT_MIN;maxPathSum(root, maxSum);return maxSum;
}

代码解释

首先定义了二叉树节点的结构体 TreeNode ，包含节点值 val 以及左右子节点指针 left 和 right 。

maxPathSum(TreeNode* root, int& maxSum) 函数用于递归计算以 root 为根节点的子树的最大路径和。它有两个返回值相关的操作：

函数内部计算当前节点能为父节点提供的最大贡献值。这是通过比较左子树和右子树的最大贡献值（如果为负数则取 0，因为负数不会增加路径和的大小），再加上当前节点的值得到的。比如，leftMax = max(0, maxPathSum(root->left, maxSum)); 就是计算左子树的最大贡献值。

同时，计算经过当前节点的路径和，即当前节点值加上左子树和右子树的最大贡献值，如 int currentPathSum = root->val + leftMax + rightMax; ，并更新全局最大路径和 maxSum 。

外层的 maxPathSum(TreeNode* root) 函数初始化全局最大路径和为最小值 INT_MIN ，然后调用内部递归函数计算并返回最终的最大路径和。

图结构上的动态规划

图的动态规划通常需要处理节点之间复杂的连接关系，常见的有拓扑排序结合动态规划来解决有向无环图的问题，或者使用记忆化搜索处理一般图。我们以 “有向无环图的最长路径” 问题为例。

问题描述

给定一个有向无环图（DAG），图中节点带有权值，找到从某个起点到其他节点的最长路径长度。

代码示例

#include <iostream>
#include <vector>
#include <queue>
using namespace std;// 拓扑排序 + 动态规划求有向无环图的最长路径
int longestPathInDAG(vector<vector<pair<int, int>>>& graph, int start) {int n = graph.size();vector<int> indegree(n, 0);  // 入度数组vector<int> dp(n, 0);  // dp[i]表示从起点到节点i的最长路径长度queue<int> q;// 统计每个节点的入度for (int i = 0; i < n; ++i) {for (auto& edge : graph[i]) {indegree[edge.first]++;}}// 将入度为0的节点入队for (int i = 0; i < n; ++i) {if (indegree[i] == 0) {q.push(i);}}while (!q.empty()) {int node = q.front();q.pop();for (auto& edge : graph[node]) {int nextNode = edge.first;int weight = edge.second;// 更新到下一个节点的最长路径长度dp[nextNode] = max(dp[nextNode], dp[node] + weight);indegree[nextNode]--;if (indegree[nextNode] == 0) {q.push(nextNode);}}}int maxPath = 0;for (int i = 0; i < n; ++i) {maxPath = max(maxPath, dp[i]);}return maxPath;
}

代码解释