根據
代碼的輸出是正確的：
MST Solution:
[0 1]: 1.000000
[2 0]: 1.000000
是不是檔案沒有更新，并且在最近的 boost 版本中，該演算法實際上可以與有向圖一起使用？
uj5u.com熱心網友回復：
我會簡化代碼Live
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>
using Graph =
boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
boost::no_property,
boost::property<boost::edge_weight_t, double>>;
using Edge = Graph::edge_descriptor;
int main()
{
Graph g(3); // 0..2
/*auto [it, ok] =*/ add_edge(0, 1, {1}, g);
add_edge(0, 2, {2}, g);
add_edge(1, 0, {1}, g);
add_edge(1, 2, {2}, g);
add_edge(2, 0, {1}, g);
add_edge(2, 1, {2}, g);
auto cost = get(boost::edge_weight, g);
std::vector<Edge> spanning_tree;
kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));
std::cout << "MST Solution:\n";
for (auto e : spanning_tree) {
std::cout << e << ": " << cost[e] << "\n";
}
}
如果您堅持使用回圈插入邊緣：Live
for (auto [i, j, c] : { std::tuple //
{0, 1, 1.},
{0, 2, 2.},
{1, 0, 1.},
{1, 2, 2.},
{2, 0, 1.},
{2, 1, 2.},
})
{
if (!add_edge(i, j, {c}, g).second)
return 255;
}
問題
如果您不滿足記錄在案的先決條件，則輸出未指定。未指定并不意味著它會引發例外（將被指定）。它甚至可能不小心（似乎）做了正確的事情。
關鍵是該演算法是在假設邊按定義可以以相同的成本反向遍歷的假設下運行的。一旦你偏離了這一點，演算法可能會給出不正確的結果。事實上，某些演算法可能會表現出未定義的行為（例如，具有某些負權重的 Dijkstra 可能永遠不會完成）。
你最好
- 將您的圖表轉換為無向圖
- 滿足無向圖的不變數，并驗證演算法是否適用于它
- 使用 MDST（最小有向生成樹）演算法，參見例如在有向圖上找到最小生成樹
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/419347.html
標籤：