Prim的算法通过邻接矩阵

Question

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

我所要做的就是编写一个算法方法，然后继续编写程序。请建议如果以下是好的？

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

   为各个VI：= 1到n做//圣维特是第i个顶点，其存储一对房子 为每个VJ：= 1到n做// Vjth是相邻对房子的一些重量 如果（Vi和VJ之间存在边缘），那么 设置 A {VI中，VJ}以w（六，VJ） 否则如果（边缘不Vi和VJ之间存在）那么 Set A [Vi，Vj]：= 0

2. 计算最小生成树。

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

Answer 1

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