How to compare nodes in minHeapify for minimum spanning tree?

Question

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!

Answer 1

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.

Consider the algorithm from Wiki as well.

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.

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

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.

Answer 2

Your heap could be of pairs <vertex, weight>, and will contain vertices, which are a single edge away from any vertex already in the partial minimum spanning tree. (edit: in some cases it may contain a vertex which is already in the partial MST, you should ignore such elements when they pop out).

It could be a heap of edges like <src, dst, weight>, which is practically the same, you just ignore src while dst is the same as vertex in the first variant.

PS. Regarding that key thing, I see no need for any keys, you need to compare weights.

Answer 3

The heap must maintain the vertices with key as the smallest weighted edge to it. As the vertex is still not visited hence any edge to it will be unvisited hence the minimum of all unvisited edge to unvisited vertex will be the next edge to be added to spanning hence you remove the vertex corresponding to it. The only problem here is to maintain the updated weights to minimum edges to a vertex in heap as the spanning tree changes in every iteration and new edges are added to it. The way to do it is to keep the position of each unvisited vertex in the heap, when a new vertex is added to spanning tree the unvisited edges from it are updated using the direct position of vertex they are pointing to using stored positions. Then you update the vertex minimum cost if the current cost is less that new edge weight added. Then bubble it up the heap using standard procedure of heap to maintain the min heap.

DataStructure: -

<Vertex,Weight> : Vertex id & weight of minimum edge to it as record of heap

position[Vertex] : The position of vertex record in heap.

Note: inbuilt function wont help you here hence you need to build your own heap to make this work efficiently.Initialize the key values of each vertex to some infinite value at the start

Another Approach: Store the all edge which point to unvisited vertex with weight in min heap. But that would require higher space complexity then other approach but has similar amortized time complexity. When you extract a edge check if the vertex it is pointing to is visited or not, if visited extract again and discard the edge.