Graph Representation using Maps

#1

I am trying to implement a weighted graph using
map<int, list<pair<int, int> > >
In the input multiple / parallel edges between x and y are possible. I wanna store only the edge with minimum weight. How to implement that?

#2

Hey
What you should do is:-
Create a map<int, list<pair<int, int> >
now let’s take an example:-
Let’s consider given edges as:
Edge no ->Edges->Weights
1->(1,2) ->4
2->(1,3) ->5
3->(1, 2)->2
4->(1,3)->4
When you get edge number 1, you first check whether a pair starting with 2 exists in the vector of 1, here it does not , so you insert pair<int, int>(2,4) in the vector of map key = 1,
When you get edge number 2, you first check whether a pair starting with 2 exists in the vector of 1, here it does not , so you insert pair<int, int>(3,5) in the vector of map key = 1,
When you get edge number 3, you first check whether a pair starting with 2 exists in the vector of 1, here it does so you update pair<int, int>(2, 4) to pair<int, int>(2, 2) in the vector of map key = 1,
When you get edge number 4, you first check whether a pair starting with 3 exists in the vector of 1, here it does so you update pair<int, int>(3, 5) to pair<int, int>(3, 4) in the vector of map key = 1,

This way you can implement this

1 Like
#3

yeah, I thought the same, but actually could not find a way to implement first check whether a pair starting with 2 exists in the vector of 1 this part, how do I check it? traverse? it will be costly then.
constraints for nodes, edges are 1000, 1000

#4

Hey
How about creating a map<int, map<int, int> > ?
Then you can easily search…

1 Like
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#6

hyee,
what about map<int,list> data structure to store noe and adjacent list with weight???

#7

hey i may be wrong , but can you explain me ,when you get edge 2 how first check whether a pair startig with 2 and not 3, exsites in vector of 1,