我在 C 中使用 Prim MST，该函数采用邻接矩阵。在 A[i][j] 中给定权重。
假设我有一个前置数组，它可以追踪我目前找到的最小边。
predecessor[u]=v {这也是最终的MST}
现在我想修改当前的 A[i][j] 矩阵并将权重更改为 1。
那是当边缘(索引)也存在于前导数组中时。
否则我将其更改为零。
我该怎么做？这是我的解决方案:
for (x....)
for (y...)
if (x!=y && (p[x]==y || p[y]==x))
set to 1
else
set to 0
最佳答案
您的伪代码是正确的，这将为您提供一个 0-1 矩阵，该矩阵表示 Prim 算法找到的树。然而，这种存储方法相当昂贵，因为它需要 O(n^2) 空间，而一棵树可以存储在 O(n) 内存中。
或者，您可以在 O(n^2) 时间内将矩阵初始化为零，然后在 O(n) 时间内添加边:
for (x ...)
for (y ...)
A[x][y] = 0
for (x ...)
if (p[x] != x)
A[x][p[x]] = A[p[x]][x] = 1
关于c - 以邻接矩阵作为参数的 Prim MST，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11637302/