数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究树中所有节点对最短路径之和
在树中，“所有节点对最短路径之和”是指计算所有节点对之间各自最短路径的总和。一种有效的方法是使用双重深度优先搜索 (DFS) 算法。在第一次 DFS 遍历中，确定所选节点与所有其他节点之间的距离。在第二次 DFS 遍历中，再次遍历树，将每个节点视为潜在的 LCA（最近公共祖先），并累加以所选 LCA 为祖先的节点对之间的距离。可以使用此方法计算树中所有节点对最短路径之和，并确保获得最优解。
使用的方法
双重深度优先搜索 (DFS) 方法
动态规划方法
双重深度优先搜索 (DFS) 方法
对于树中所有节点对最短路径之和，我们使用双重深度优先搜索 (DFS) 方法，该方法涉及两次 DFS 遍历。首先，我们从任何节点开始计算到所有其他节点的距离。然后，在第二次 DFS 遍历期间，我们遍历树，同时将每个节点视为潜在的 LCA。在遍历过程中，我们计算并累加以所选 LCA 为后代的节点对之间的距离。通过对所有节点重复此过程，我们得到所有节点对最短路径的总和。这种方法对于此问题非常有效，因为它可以有效地计算树中所有节点对之间的距离之和。
算法
树中的任何节点都可以作为起始节点。
执行从该节点开始的深度优先搜索 (DFS)，以确定从所选起始节点到所有其他节点的距离。这些距离应该存储在数组或数据结构中。
接下来，在树上运行第二次 DFS，将每个节点视为潜在的 LCA（最近公共祖先）。
在第二次 DFS 遍历树的过程中，计算以所选 LCA 为后代的节点对之间的距离。将这些距离加总到每个 LCA 中。
对树中的每个节点重复此过程。
步骤 4 中计算的所有距离之和表示树中所有匹配的最短路径的总和。
示例
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 10005;
vector<int> graph[MAXN];
int ancestor[MAXN];
int dfs(int node, int lca, int distance) {
int sum = 0;
for (int neighbor : graph[node]) {
if (neighbor != lca) {
sum += dfs(neighbor, lca, distance + 1);
}
}
return sum + distance;
}
int main() {
int lca_node = 0;
int total_sum = 0;
for (int node = 0; node < MAXN; ++node) {
if (node != lca_node) {
total_sum += dfs(node, lca_node, 0);
}
}
cout << "Total sum of distances between descendants of the LCA: " << total_sum << endl;
return 0;
}
输出
Total sum of distances between descendants of the LCA: 0
动态规划方法
在树中所有节点对最短路径之和的动态规划方法中，我们首先选择任何节点作为根节点，并将树转换为有根树。我们使用动态规划计算每个节点到根节点的距离，然后将结果存储在数组中。然后，对于每个节点，我们将其子节点到根节点的距离（已计算）加总起来，以计算所有其他节点的总距离。这样，我们就可以快速计算所有节点对最短路径的总和。该算法具有 O(N) 的时间复杂度，其中 N 是树中的节点数，是一种高效的解决方案。
算法
将树中的任何节点设为根节点，并对树进行根化（例如，使用根节点的深度优先搜索）。
可以使用动态规划来计算每个节点到根节点的距离。这些距离应存储在数组或数据结构中。
计算树中每个节点到所有其他节点的总距离
最终结果是树中所有节点对最短路径的总和。
a. 遍历当前节点的子节点。
b. 为了考虑经过当前节点的路径，将每个子节点的子树中的节点数以及之前为每个子节点计算的到根节点的距离加总起来。
c. 将这些总和加总到当前节点的每个子节点上。
d. 将当前节点的总和加到最终结果中。
#include <iostream>
#include <vector>
using namespace std;
struct TreeNode {
int val;
vector<TreeNode*> children;
};
int dfs(TreeNode* node, vector<int>& distances) {
int subtree_size = 1;
for (TreeNode* child : node->children) {
subtree_size += dfs(child, distances);
distances[node->val] += distances[child->val] + subtree_size;
}
return subtree_size;
}
int sumOfAllPairShortestPaths(TreeNode* root) {
vector<int> distances(root->val + 1, 0);
dfs(root, distances);
int total_sum = 0;
for (int distance : distances) {
total_sum += distance;
}
return total_sum;
}
int main() {
TreeNode* root = new TreeNode{0};
int result = sumOfAllPairShortestPaths(root);
cout << "Sum of all pair shortest paths in the tree: " << result << endl;
return 0;
}
输出
Sum of all pair shortest paths in the tree: 0
结论
可以使用双重深度优先搜索 (DFS) 方法或动态规划计算树中所有节点对最短路径之和。双重 DFS 方法包括两次遍历，其中我们首先计算从所选节点到所有其他节点的距离，然后在将每个节点视为潜在的最近公共祖先 (LCA) 时再次遍历树，以累加后代节点对之间的距离。动态规划方法涉及递归使用 DFS 对树进行根化并计算从根节点到每个其他节点的距离。两种方法的结果相同，都包含树中所有节点对最短路径的总和。两种算法都可以提供有效的解决方案，在选择算法时可以根据具体的实现偏好或树结构来决定。
391 次查看
