Designing Data structures for Prim's implementation in c++

Question

I am trying to implement Prim's algorithm for MST in C++. I have a design question

I implemented a min-heap which takes an integer and we can extract-min, decrease key and insert-key.

Now as i understand in Prim's I need to maintain weight, neighbor information for each vertex. Some ideas i have are:

1] Define a structure

struct node {
    int vertex;
    int weight;
    int neighbor;
};

Use the min heap to return the node with minimum weight. But the problem is decrease key, since for decrease key the caller needs to pass the vertex for which he wants to decrease key. Since heap swaps elements too often, I have to go through the entire list to find the vertex and then decrease its key. This is O(n), I think Prim's would get worse if i do this.

2] The other way, would be to maintain another array, which tracks the position of a vertex in the min-heap queue. But it would be cumbersome to track positions during min-heap operations.

Basically, If i have to do decrease-key(v), how to find v in min-heap queue which is based on weight. So is there any elegant way to do this? which can still retain the complexity?

Ami Tavory · Accepted Answer · 2015-05-16 07:28:40Z

You basically indeed need to do some cross referencing between data structures. However, you write

But it would be cumbersome to track positions during min-heap operations

which is not quire correct. Using the following, you can reuse or write reusable data structures which do not require this.

To begin with, your priority queue needs to expose some sort of iterator, which allows O(1) access. For this, you can use boost.Heap directly (see note below), or get the idea from there on how the interface should look.
Now you use another data structure which maps (in O(1)) node labels to the queue's iterators. E.g., if node labels are (consecutive) integers, you can use a vector of iterators; if they are basically anything else, you should probably use an unordered_map.
Each node structure also needs to include the label used by the data structure in 2.

Item 3. means that you need to add the following to your code above.

struct node {
     ...
     // Identifies
     Label label;
};

Note how this allows you to decouple the priority queue from the other data structure. When you do a decrease_key, and your node moves around in the priority queue, you don't need to worry about anything, as each node contains the label member.

Having said all of that, you should also consider simply using the Boost Graph Library which already has Prim's algorithm.

Collectives™ on Stack Overflow

Designing Data structures for Prim's implementation in c++

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related