資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學查詢具有交替顏色邊的最小生成樹
程式碼執行計算，透過替換彩色邊來查詢最小生成樹。它採用動態規劃方法來計算最小成本。該演算法考慮所有可能的邊和顏色，並根據是否保持交替顏色模式遞迴地評估新增或刪除每條邊的成本。它使用記憶化方法跟蹤迄今為止遇到的最小成本。該演算法透過貪婪地選擇成本最低的邊來構建最小生成樹，確保相鄰邊具有不同的顏色。最後，它返回構建的最小生成樹中的最小成本。
使用的方法
最小成本生成樹 (MCST) 方法。
最小成本生成樹
最小成本生成樹是一種圖演算法，它找到連線圖所有頂點的成本最低的樹。它迭代地選擇不會形成環路的最低成本邊，直到所有頂點都連線起來。該演算法維護一組已訪問的頂點，並跟蹤到達每個頂點的最小成本。它在每一步都貪婪地選擇成本最低的邊，擴充套件樹直到所有頂點都被包含在內。生成的樹在圖上所有可能的生成樹中具有最低成本。
演算法
從一個空樹 T 和一組已訪問頂點 V 開始。
將每個頂點的最小成本初始化為無窮大，除了起始頂點，其設定為 0。
當 V 不包含所有頂點時，
選擇不在 V 中的頂點 u，其具有最小成本。
將 U 新增到 V。
對於 u 的每個相鄰頂點 v
如果 v 不在 V 中，並且邊 (u, v) 的成本小於 v 的當前最小成本，
用邊 (u, v) 的成本更新 v 的最小成本。
將邊 (u, v) 新增到 T。
返回樹 T，它表示最小成本生成樹。
此演算法迭代地選擇未訪問頂點中成本最低的頂點，並透過新增與該頂點關聯的最低成本邊來擴充套件樹。它繼續此過程，直到所有頂點都包含在樹中。生成的樹在圖上所有可能的生成樹中將具有最低成本。
示例
#include <iostream>
#include <vector>
#include <climits>
long long calculateMinCost(int numVertices, int mask, int prevVertex, int prevColor, const std::vector<std::vector<std::pair<int, char>>>& graph, std::vector<std::vector<std::vector<long long>>>& dp) {
if (mask == ((1 << numVertices) - 1)) {
return 0;
}
if (dp[mask][prevVertex][prevColor] != -1) {
return dp[mask][prevVertex][prevColor];
}
long long ans = LLONG_MAX;
for (int i = 0; i < numVertices; i++) {
for (const auto& edge : graph[prevVertex]) {
int nextVertex = edge.first;
char nextColor = edge.second;
if (!(mask & (1 << nextVertex)) && (nextColor != prevColor)) {
long long z = calculateMinCost(numVertices, mask | (1 << nextVertex), nextVertex, nextColor, graph, dp);
if (z != LLONG_MAX) {
ans = std::min(ans, z);
}
}
}
}
return dp[mask][prevVertex][prevColor] = ans;
}
void makeGraph(const std::vector<std::pair<std::pair<int, int>, std::pair<int, char>>>& edges, int numVertices, std::vector<std::vector<std::pair<int, char>>>& graph) {
for (const auto& edge : edges) {
int u = edge.first.first - 1;
int v = edge.first.second - 1;
int cost = edge.second.first;
char color = edge.second.second;
graph[u].emplace_back(v, color);
graph[v].emplace_back(u, color);
}
}
int getMinimumCost(int numVertices, const std::vector<std::vector<std::pair<int, char>>>& graph) {
std::vector<std::vector<std::vector<long long>>> dp(1 << numVertices, std::vector<std::vector<long long>>(numVertices, std::vector<long long>(3, -1)));
long long minCostValue = LLONG_MAX;
for (int i = 0; i < numVertices; i++) {
minCostValue = std::min(minCostValue, calculateMinCost(numVertices, 1 << i, i, 'B', graph, dp));
minCostValue = std::min(minCostValue, calculateMinCost(numVertices, 1 << i, i, 'W', graph, dp));
}
if (minCostValue != LLONG_MAX) {
return static_cast<int>(minCostValue);
} else {
return -1;
}
}
int main() {
int numVertices = 3;
std::vector<std::pair<std::pair<int, int>, std::pair<int, char>>> edges = {
{ { 1, 2 }, { 2, 'B' } },
{ { 1, 2 }, { 3, 'W' } },
{ { 2, 3 }, { 4, 'W' } },
{ { 2, 3 }, { 5, 'B' } }
};
std::vector<std::vector<std::pair<int, char>>> graph(numVertices);
makeGraph(edges, numVertices, graph);
std::cout << getMinimumCost(numVertices, graph) << '\n';
return 0;
}
輸出
0
結論
本文介紹了一種演算法方法，用於在給定圖中透過替換彩色邊來查詢最小生成樹 (MST)。該問題包括以相鄰邊具有不同顏色且所選邊的總成本最小化的方式選擇邊。該演算法利用動態規劃來計算每種可能的頂點和顏色組合的最小成本，並使用記憶化來避免冗餘計算。
程式碼執行演示了該演算法，併為具有彩色邊的示例圖提供瞭解決方案。本文還解釋了最小成本生成樹 (MCST) 的概念及其在圖論中的重要性。總的來說，本文作為理解和實現查詢具有交替彩色邊的最小生成樹演算法的全面指南。
78 次瀏覽
