Prim的算法通过邻接矩阵

Question

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

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

1. 设置邻接矩阵A {Vi，Vj}。这里Vi包含所有访问过的节点，Vj包含所访问的Vi的所有相邻节点。矩阵下方将存储与其相邻房屋相隔一定距离的所有房屋。我很困惑 对于每个Vi：= 1到n do // Vith是第i个顶点，它为每个Vj存储一对房屋：= 1到n do // Vjth是具有一些权重的相邻房屋对（如果在Vi和之间存在边缘） Vj）然后用w（Vi，Vj）设置A {Vi，Vj}否则如果（Vi和Vj之间不存在边）则设置A [Vi，Vj]：= 0
2. 计算最小生成树。
3. 输出：显示所需的总水管道。

Answer 1

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

Answer 2

1. 是的，使用邻接矩阵是实现Prim算法构建最小生成树的可行方法。运行时间为O（V ^ 2）。更具体地说，你将有一个嵌套的for循环，外循环花费O（V），这是每次它以最小成本添加到MST来获取顶点。因此，为此，您必须创建一个关键数组key [v]，以保持顶点添加到树的成本。还有一个数组mst [v]，以确保在每次迭代后，应访问一个顶点 然后内部for循环，基于prim的算法，每次在拾取顶点v后，用最小成本键[v]，添加到当前mst，在将mst [v]标记为已访问之前，您应该做什么？您应该使用“邻接矩阵”来比较/更新v的邻居添加到mst的成本。这很重要，因此每当它选择一个顶点并将其添加到树中时，Prim将通过它从v获得的信息更新顶点添加到mst的成本。所以下次它以最小成本再次获取u，并且它再次重复，直到发现所有顶点，mst [v]将全部为真。因此，在内部for循环中，它使用表示v的行并检查v的所有邻居，它们都是行中的所有列。如果w [i] [j]小于当前顶点j的加法成本，则为密钥[j]。然后使用v到该顶点的权重作为该顶点的加法成本，key [j] = w [i] [j]。在访问了所有v的邻居之后，将v标记为已完成。 所以prim是明确的，最好将“不存在的”边设置为0的权重，因此在矩阵中，w [i] [j] = 0，这意味着顶点i和顶点j不能从每个另外，每次你拿起av并且应该检查它的邻居，它只看正值。此外，矩阵的对角线应设置为全零，因为当有理由计算添加已经在mst中的顶点到mst的成本。总之，如果每次prim检查v的邻居w [i] [j] <key [j]，当前的加法成本，则key [j] = w [i] [j]。 该算法的运行时间，O（V）设置所有数组初始化，设置键[root] = 0，以及其他顶点，key [v] = inf，infinity将成本添加到mst，mst [v]为null。 然后O（V）用于外循环迭代，然后在外循环内，每次以最小成本获取顶点v，因此它花费O（V），使用min-heap可能更好。然后检查v的所有邻居，它将是O（E），包括所有的考试。因此迭代成本：O（V）*（V）+ O（E），并且prim的算法成本可以由O（V ^ 2）限制