c - 以邻接矩阵为参数的 Prim MST

Question

我正在使用 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

score 2 · Accepted Answer

您的伪代码是正确的，这将为您提供一个 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

1 回答 1