#define ll long long
ll prims(int n)
{
ll ans;
vector<bool> used (n);
#define INF 1000000000000LL
vector<ll> min_e (n, INF), sel_e (n, -1);
min_e[0]=-1*INF;
ll dis=1;
for(int i=0;i<n;i++)
{
int v=-1;
for(int j=0;j<n;j++)
{
if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
v = j;
}
used[v] = true;
if(sel_e[v]!=-1)
cout << v << " " << sel_e[v] << endl;
for (int to=0; to<n; ++to)
if (g[v][to] < min_e[to]) {
min_e[to] = g[v][to];
sel_e[to] = v;
}
}
for(int i=0;i<n;i++) cout<<i<<" "<<sel_e[i]<<" "<<g[i][sel_e[i]]<<endl;
return dis;
}
我正在尝试将 Prim 的算法应用于负边权重的密集无向图,但我无法理解为什么它在几乎所有情况下都会产生错误的输出。 我正在使用邻接矩阵 g[N][N] 来存储边缘。
实际上,我当前代码的输出是一个带循环的最小生成树。为什么循环检查机制不起作用?
最佳答案
其实问题就出在这里:
for (int to=0; to<n; ++to)
if (g[v][to] < min_e[to]) {
min_e[to] = g[v][to];
sel_e[to] = v;
}
}
如果 to
尚未被访问,您应该只更新 sel_e
和 min_e
。
否则,考虑这种情况:
0 -- 1 -- 2
其中 w({0, 1}) = 10
和 w({1, 2} = 1)
。你会设置 sel_e[1] = 2
,即使你需要 sel_e[1] = 0
。
关于c++ - 我在实现 Prim 最小生成树算法时的逻辑错误是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15910337/