以邻接矩阵为参数的Prim MST

我正在C中使用Prim MST，并且该功能需要一个邻接矩阵。鉴于当然在A[i][j]的重量。以邻接矩阵为参数的Prim MST

假设我有一个前驱数组，跟踪我迄今为止发现的最小边。 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

2012-07-24 ms. sakura

看起来正确的...什么是您的实际问题？ – Spudd86 2012-07-24 19:04:42

我不完全确定还有什么要检查：S你会怎么做？ – 2012-07-24 19:08:07

就像你做的那样......或者可能是在sdcwc的回答中 – Spudd86 2012-07-25 17:51:44

您的伪代码是正确的，这会给你一个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

2012-07-24 19:26:04 sdcvvc

回答