我正在尝试使用 prim 算法创建一个最小生成树，但我对实际堆有一个主要问题。我将我的图形邻接列表构造为顶点向量，每个顶点都有一个边向量。边包含权重、连接顶点和键。我不确定我的堆是否应该是一堆顶点或边。如果我将其设为顶点堆，则无法确定权重是否来自相同的父顶点和目标顶点，这使我认为我应该为每个顶点的边列表创建一个堆。所以我的最后一个问题是我应该创建一堆边还是一堆顶点？如果它是一个边列表，我应该使用边上的权重作为键，还是应该有一个单独的数据成员，称为键，我可以实际用于优先级队列？谢谢！
问问题
276 次
3 回答
0
堆必须保持以键为最小加权边的顶点。由于顶点仍然没有被访问，因此它的任何边缘都将未被访问，因此所有未访问的边缘到未访问的顶点的最小值将是下一个要添加到跨越的边缘，因此您删除对应于它的顶点。这里唯一的问题是在每次迭代中生成树都会发生变化并添加新边时，将更新后的权重保持为堆中顶点的最小边。这样做的方法是保持堆中每个未访问顶点的位置，当将新顶点添加到生成树时，使用存储位置指向的顶点的直接位置更新来自它的未访问边。然后，如果当前成本小于添加的新边权重，则更新顶点最小成本。
数据结构： -
<Vertex,Weight> : Vertex id & weight of minimum edge to it as record of heap
position[Vertex] : The position of vertex record in heap.
注意：内置函数在这里对您没有帮助，因此您需要构建自己的堆以使其有效地工作。在开始时将每个顶点的键值初始化为某个无限值
另一种方法：将所有指向未访问顶点的边存储在最小堆中。但这将需要比其他方法更高的空间复杂度，但具有类似的摊销时间复杂度。当您提取边缘时，检查它指向的顶点是否被访问，如果访问过，则再次提取并丢弃边缘。
于 2013-12-15T06:51:22.403 回答
0
您应该创建一个 minHeap 边，因为您要按边的权重对边进行排序，但边应包含两个顶点：每端代表一个顶点。否则，正如您所建议的：无法确定权重是否来自相同的父顶点和目标顶点。因此，您应该重新构建您的边缘类并制作它们的 minHeap。
也考虑一下来自Wiki的算法。
用从图中任意选择的单个顶点初始化一棵树。
让树增长一条边：在将树连接到树中尚未存在的顶点的边中，找到最小权重边，并将其转移到树上。
重复步骤 2（直到所有顶点都在树中）。
我不完全理解边缘类中的关键字段。我认为这就像一个边缘的身份。所以你应该把它们堆起来，但是由于你向堆提供了用户定义的数据结构，你还应该为边缘类提供一个比较函数，即定义bool operator<(const Edge&)方法。
于 2013-12-14T21:41:44.303 回答
0
您的堆可能是对的<vertex, weight>，并且将包含顶点，这些顶点与部分最小生成树中已经存在的任何顶点相距一条边。（编辑：在某些情况下，它可能包含一个已经在部分 MST 中的顶点，当它们弹出时你应该忽略这些元素）。
它可能是一堆边缘，例如<src, dst, weight>，实际上是相同的，您只需忽略它src，而与第一个变体中dst的相同vertex。
PS。关于那key件事，我认为不需要任何键，您需要比较权重。
于 2013-12-14T21:16:45.703 回答