我想用Prim算法创建一个最小生成树和我有实际的堆的一个主要问题。余结构我的图形邻接表成为顶点的向量，并且每个顶点有边缘的向量。边缘包含一个重量，连接顶点，和一个键。我不知道我的堆是否应顶点或边一堆。如果我让顶点一堆那么有没有办法来确定是否砝码由相同的父和目的地顶点，这让我觉得我应该做一个堆边的每个顶点列表去。所以，我的最后一个问题是，我应该创建一个堆边，或顶点一堆？如果其边缘名单，我应该使用的重量上的边缘为重点，或者我应该有一个单独的数据成员称为关键，我可以实际使用的优先级队列？谢谢！

I am trying to create a minimum spanning tree using prim's algorithm and I have a major question about the actual heap. I structured my graphs adjacency list to be a vector of vertexes, and each vertex has a vector of edges. The edges contain a weight, a connecting vertex, and a key. I am not sure whether my heap should be a heap of vertexes or edges. If I make it a heap of vertexes then there is no way to determine whether the weights are going from the same parent and destination vertexes, which makes me think that I should be making a heap for each vertexes list of edges. So my final question is should I be creating a heap of edges, or a heap of vertexes? If its a list of edges, should I be using the weight on the edges as the key, or should I have a separate data member called key that I can actually use for the priority queue? Thanks!

推荐答案

您应该边缘的minHeap，因为你要通过自己的体重进行排序的边缘但是的边缘应该包含两个顶点：重presenting一个顶点的两端。否则，如你提示：没有办法确定是否砝码由相同的父和目的地顶点去。因此，你应该重新构造的边缘类，使他们的minHeap。

You should make a minHeap of edges since you are going to sort edges by their weight but the edges should contain two vertexes: representing one vertex on each end. Otherwise, as you suggested: there is no way to determine whether the weights are going from the same parent and destination vertexes. Therefore you should re-structure your edge class and make a minHeap of them.

考虑从算法维基的为好。

初​​始化树的一个顶点，选择   任意地从曲线图。

Initialize a tree with a single vertex, chosen arbitrarily from the graph.

由一个边缘成长树：边缘   在树连树顶点还没有，找到   最小权重的边缘，并将其转移到树中。

Grow the tree by one edge: Of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.

重复步骤2（直到所有的顶点是在树）。

Repeat step 2 (until all vertices are in the tree).

我不完全理解的边缘类的关键领域。我认为它就像一个ID的边缘。所以你应该让他们一堆，但由于您提供用户自定义的数据结构堆，你也应该提供一个比较函数的边缘类，即定义布尔运算符＆LT;（常量边及放大器; ）方法。

I don't fully understand the key field in the edge class. I assume it's like an Id to the edge. So you should make a heap of them but since you are providing user-defined data structure to the heap, you should also provide a comparison function for the edge class, i.e. define the bool operator<(const Edge&) method.