資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究樹中所有節點對之間最小邊權重的乘積
樹中所有節點對之間最小邊權重的乘積可以透過找到樹中每對可能的頂點之間的最小權重邊，然後將所有這些最小權重相乘來獲得。這個值代表了從樹中的任何一個頂點到另一個頂點的最小可能成本或權重。透過考慮每條邊的最小權重，我們確保找到樹中任意兩個頂點之間的最有效路徑。這些最小邊權重的乘積提供了樹結構整體連通性和效率的緊湊指標。
使用的方法
深度優先搜尋 (DFS)
Prim 演算法
深度優先搜尋 (DFS)
樹中所有節點對之間最小邊權重的乘積可以使用深度優先搜尋 (DFS) 方法來找到。從任何一個節點開始，我們以深度優先的方式遍歷樹，先探索每個分支，然後再回溯。在遍歷過程中，我們維護一個迄今為止遇到的最小邊權重的執行乘積。每當我們遇到一條新的邊時，我們將它的權重與當前最小權重進行比較，並在必要時更新乘積。透過訪問樹中的所有節點，我們確保考慮所有節點對並有效地利用 DFS 計算最小邊權重的最終乘積。
演算法
從樹中的任何一個節點開始進行 DFS 遍歷。
將一個變數“product”初始化為 1，表示迄今為止遇到的最小邊權重的乘積。
在以深度優先的方式遍歷樹時，跟蹤從當前節點到其父節點的路徑上看到的最小邊權重。如果新邊權重小於當前最小值，則相應地更新“product”。
一旦 DFS 遍歷完成，“product”將儲存樹中所有節點對之間最小邊權重的乘積。
返回“product”作為最終結果。
示例
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Structure to represent a node in the tree
struct Node {
int value;
vector<Node*> children;
};
// Helper function for DFS traversal
void dfs(Node* node, int& product, int minWeight) {
// Update the product if the minimum weight is smaller
if (node->value < minWeight) {
product *= node->value;
minWeight = node->value;
}
// Recursively explore all children nodes
for (Node* child : node->children) {
dfs(child, product, minWeight);
}
}
// Function to calculate the product of minimum edge weights between all pairs of nodes
int calculateProduct(Node* root) {
int product = 1;
int minWeight = INT_MAX;
dfs(root, product, minWeight);
return product;
}
int main() {
// Create a sample tree
Node* root = new Node({4, {}});
Node* node1 = new Node({2, {}});
Node* node2 = new Node({6, {}});
Node* node3 = new Node({3, {}});
Node* node4 = new Node({5, {}});
Node* node5 = new Node({1, {}});
Node* node6 = new Node({7, {}});
root->children = {node1, node2};
node1->children = {node3, node4};
node2->children = {node5, node6};
// Calculate the product of minimum edge weights
int result = calculateProduct(root);
// Print the result
cout << "Product of minimum edge weights: " << result << endl;
// Deallocate memory
delete root;
delete node1;
delete node2;
delete node3;
delete node4;
delete node5;
delete node6;
return 0;
}
輸出
Product of minimum edge weights: 8
Prim 演算法
Prim 演算法透過從一個任意頂點開始，並不斷新增連線樹中頂點到樹外頂點的最小權重邊來找到樹中所有節點對之間最小邊權重的乘積。此過程持續到所有頂點都包含在樹中。在每個步驟中，演算法選擇連線樹到不在樹中的頂點的最小權重邊，確保樹保持連線並且邊權重最小化。最終乘積是所有選定邊的權重之積。
演算法
建立一個包含頂點和邊的圖表示，並初始化一個空集來儲存生成的樹。
任意選擇一個起始頂點，並將其包含在生成樹的集合中。
當生成樹不包含所有頂點時，
找到連線生成樹中頂點到樹外頂點的最小權重邊。
將樹外的頂點新增到生成樹集合中，並將選定的邊新增到樹中。
計算生成樹中所有邊權重的乘積。
示例
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
typedef pair<int, int> pii;
typedef vector<vector<pii>> Graph;
void addEdge(Graph& graph, int src, int dest, int weight) {
graph[src].push_back(make_pair(dest, weight));
graph[dest].push_back(make_pair(src, weight));
}
int primMST(Graph& graph) {
int numVertices = graph.size();
vector<bool> visited(numVertices, false);
vector<int> minWeight(numVertices, INT_MAX);
minWeight[0] = 0; // Start from vertex 0
int product = 1;
for (int count = 0; count < numVertices - 1; ++count) {
int minIndex = -1;
int minWeightValue = INT_MAX;
// Find the vertex with the minimum weight
for (int v = 0; v < numVertices; ++v) {
if (!visited[v] && minWeight[v] < minWeightValue) {
minWeightValue = minWeight[v];
minIndex = v;
}
}
visited[minIndex] = true;
// Update the minimum weights of adjacent vertices
for (const auto& neighbor : graph[minIndex]) {
int v = neighbor.first;
int weight = neighbor.second;
if (!visited[v] && weight < minWeight[v]) {
minWeight[v] = weight;
}
}
product *= minWeightValue;
}
return product;
}
int main() {
int numVertices = 5;
int numEdges = 7;
Graph graph(numVertices);
// Add edges to the graph
auto addEdge = [&](int src, int dest, int weight) {
graph[src].push_back({dest, weight});
graph[dest].push_back({src, weight});
};
addEdge(0, 1, 2);
addEdge(0, 2, 3);
addEdge(1, 3, 4);
addEdge(1, 4, 5);
addEdge(2, 3, 1);
addEdge(2, 4, 3);
addEdge(3, 4, 6);
int minProduct = primMST(graph);
cout << "Product of minimum edge weights: " << minProduct << endl;
return 0;
}
輸出
Product of minimum edge weights: 0
結論
本文闡述瞭如何計算樹中所有節點對之間最小邊權重的乘積。它探討了兩種方法：DFS（深度優先搜尋）和 Prim 演算法。DFS 方法包括以深度優先的方式遍歷樹，跟蹤遇到的最小邊權重，並適當地更新乘積。另一方面，Prim 演算法從一個選定的頂點開始，並迭代地新增連線樹到樹外頂點的最小權重邊，最終產生所有選定邊權重的乘積。這兩種策略都用 C 語言的演算法和示例程式進行了說明。
123 次檢視
