資料結構
網路
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 次檢視
