How to implement Prim's algorithm using STL ?

I am trying to implement a data structure which is a combination of both a heap and an unordered map. The heap will hold the graph node , containing the identifier and the cost. I use the min_extract function to get the node to expand next in log(n) time. [ I am implementing the heap using std::vector and std::make_heap , pop_heap etc from algorithm ]

The unordered map holds the node , position in the vector mapping. The unordered map is used to support contains and update-node functions. But for me to do this, I need the mapping between the node and its position in the vector, otherwise I am forced to do a linear search for the item.

Even more worrying is the case, where I push or pop an item, and call the push_heap or pop_heap, this will shift around the node in the vector and the positions that I maintain in the map, will end up being wrong.

So how can I implement the functionality, where I can maintain a mapping between the node and its position.

    void push(T elem) // This will 0(n)... As the element has to be found
    {
        heapVec_.push_back(elem); // add tp vec

        std::push_heap<compar_> (heapVec_.begin() , heapVec_.end());
        // sort ? or just find in the vec ? 
        std::size_t pos = 0 ;

        // find position of the item in the vector
        std::find_if(heapVec_.begin() , heapVec_.end() , [&pos , &elem](const T& item)
                {

                    if(item == elem)
                    {
                        return true;
                    }
                    else
                    {
                        ++pos;
                    }
                });


        // add to map
        heapMap_.emplace_back(elem , pos); // how to keep track of the element where this object is added to ? 

    }   

The data structure I am looking for has to support : find min : O(lg n) contains : O(1) update-node : O(lg n) insert : O(lg n)

It will be trivial to implement if I roll out my own heap where when I do the bubble up or down, I update the positions of the node in the map. Before I do that I wanted to make sure that I couldn't do it in STL.

---

If you put edges into your priority queue instead of nodes, then you don't need that update-node function, and everything gets a whole lot easier.

Use some kind of set implementation to keep track of which vertices are in the tree.

Use a priority queue to maintain an ordered queue of possible edges.

Then:

Add an initial vertex to the set, and add its edges to the priority queue

Remove the cheapest edge E from the priority queue.

If one of E's vertices V is not in the tree, then add E and V to the tree. V goes in your set. If V has any edges to nodes that aren't in the set, then add those edges to the priority queue.

Go back to step 2 until the queue is empty.

链接地址: http://www.djcxy.com/p/63836.html

上一篇: 代码高尔夫：验证数独网格

下一篇: 如何使用STL实现Prim的算法？