1

我正在考虑使用 Prim 的算法来优化水管问题。当找到具有相邻顶点的边时，我非常困惑如何初始化邻接矩阵。每当存在优势时，我都会考虑增加重量。然而，w(Vi,Vj) 本身看起来是一个权重矩阵。那么，为什么我首先需要 A{Vi,Vj}。

我打算做的只是编写一种算法方法，然后继续编写程序。请建议以下是否可以？

  1. 设置邻接矩阵 A{Vi,Vj}。这里 Vi 包含访问过的所有节点，Vj 包含访问过的与 Vi 相邻的所有节点。下面的矩阵将存储通过一定距离与相邻的一对房屋相连的所有房屋对。我很困惑

    for each Vi:=1 to n do //Vith 是存储一对房子的第 i 个顶点 对于每个 Vj:=1 to n do //Vjth 是相邻的一对有一定权重的房子 if (edge 存在于 Vi 和Vj) 然后 用 w(Vi,Vj)设置A{Vi,Vj} else if (Vi 和 Vj 之间不存在边) 然后 设置A[Vi,Vj]:=0

  2. 计算最小生成树。

  3. 输出：显示所需的总水管。
4

2 回答 2

0

在您的问题中的图形算法中，如果给出了权重，则除了权重之外，通常不会对邻接进行显式编码。相反，该图被认为是一个完整的图（即每个顶点都与任何其他顶点相邻），但对于不相邻的顶点u，v在初始图中，权重被编码为“无穷大”，编码为最大值使用的数据类型，在计算等中识别的一些负值。使用这种方法，不可行的边将永远不会被考虑在内，因为它们比初始问题的任何可行解决方案都更昂贵。

于 2014-05-21T12:33:02.930 回答
0
  1. 是的，使用邻接矩阵是实现 Prim 算法构建最小生成树的一种可行方法。运行时间为 O(V^2)。更具体地说，您将有一个嵌套的 for 循环，外部循环的成本为 O(V)，即每次它拾取具有最小成本的顶点时都会添加到 MST。因此，为此，您必须创建一个键数组 key[v]，以保持将顶点添加到树的成本。还有一个数组 mst[v] 以确保在每次迭代后，应该访问一个顶点
    1. 然后内部的for循环，基于prim的算法，每次拾取顶点v后，用最小代价key[v]添加到当前mst，在将mst[v]标记为已访问之前下一步该怎么做? 您应该使用“邻接矩阵”来比较/更新 v 的邻居添加到 mst 的成本。这很重要，所以每当它选择一个顶点并将其添加到树中时，Prim 将通过它从 v 获得的信息更新顶点添加到 mst 的成本。所以下次它再次以最小成本拾取 u，并且它只是再次重复直到发现所有顶点，mst[v] 将全部为真。因此，在内部 for 循环中，它使用表示 v 的行并检查 v 的所有邻居，即行中的所有列。如果说 w[i][j] 小于顶点 j 的当前添加成本，则 key[j]。然后使用 v 对该顶点的权重作为该顶点的添加成本，key[j] = w[i][j]。并且在访问了 v 的所有邻居之后，将 v 标记为已完成。
    2. 所以prim的很清楚，最好将“不存在”的边设置为0的权重，所以在矩阵中， w[i][j] = 0 ，这意味着顶点 i 和顶点 j 不能从每个到达其他，每次你拿起 av 并检查它的邻居时，它只看正值。此外，矩阵的对角线应该设置为全零，因为当有理由计算将已经在 mst 中的顶点添加到 mst 的成本时。综上所述，如果每次 prim's 检查 v 的邻居，w[i][j] < key[j]，当前添加成本，那么 key[j] = w[i][j]。
    3. 该算法的运行时间，O(V)设置所有数组初始化，设置 key[root] = 0 和其他顶点，key[v] = inf，infinity 添加成本到 mst，并且 mst[v] 为 null。
      然后O(V)用于外循环迭代，然后在外循环内，每次以最小成本拾取一个顶点 v，因此成本 O(V)，使用最小堆可能会更好。然后检查 v 的所有邻居。将 O(E) 包括所有检查。所以迭代成本：O(V)*(V) + O(E)，prim 的算法成本可以由 O(V^2) 限制
于 2019-04-21T15:31:08.593 回答