hackerbaba's blog

Implementation of some ds for graphs
By hackerbaba, history, 4 years ago, In English

Hello again. I am newbie learning graphs, currently doing it in c++ and there are multiple opinions everywhere as to what should be used to implement the (min heap) structure(currently looking into Dijkstra's algo). 1. Should it be PRIORITY QUEUE or MULTISET or SET.? 2. How should the weighted graph be represented in the adjacency list? Currently I started doing a vector<pair<int, int> > with the node as the first element and the weight as the second. Is it right or something else has to be added?

Any other good practices for graphs are appreciated.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Well, the implementation of dijkstra algorithm can be done by both priority_queue and set and mostly it depends on the question itself. If we just need the minimum distance, priority queue is prefered but on the other hand if we need some deletion from the heap or updating some node from the heap, the set if preffered.

Second, the implementation of the adjacency list is on to one's preference but my tip is when we need some more information regarding the edge(not only weight) like it's index, special characteristics depending on the question, one should make a structure to store all the information. You can use vector<pair<int, int>> as well if you need only the destination node and the edge's weight.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks that was helpful

    So if more info is needed, and i made a struct, a vector of the struct will do. right? And as the below comment points out, a set and not a multiset ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, vector of struct will do. Make the struct like this:

      struct node
{
    int to, wt, other; 
    node(int to, int wt, int other)
    {
        this->to = to;
        this->wt = wt;
        this->other = other;
    }
};

      and make adjacency list like vector<node> v(MAX_SIZE)

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Generally avoid using $$$multiset$$$. It is fairly slow compared to $$$priority$$$ $$$queue$$$.

Do not use containers like $$$unordered$$$ $$$map$$$ and $$$unordered$$$ $$$set$$$, unless you have a custom hashing function. Some tests are specifically made to make these take $$$O(n)$$$ per operation.

In a div3 contest once I got TLE because I used an $$$unordered$$$ $$$set$$$. After the contest I changed it to $$$set$$$ and it worked.

→ Reply