trunghieu11's blog

Can we use Map of Map for storing weighted graph?
By trunghieu11, history, 9 years ago, In English

As I know one of ways for storing a weighted graph is using Adjacency List but cons of this solution is when we want to get weight of a pair vertex this will cost O(n) by looping the adjacency vertex.

So I have a solution to improve that by using Map<NodeID, Map<NodeID, Weight>> then when we want to get weight of a pair vertex, for example (1, 2) we just call Node[1].get(Node[2]), this only cost O(1).

Is this correct? I'm using Java so can it have a risk?

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does map in Java work at O(1)? I think it works at O(logN^2)

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

store graph in two ways at the same time 1- Adjacency List for algorithms like dfs and bfs

2- map of pair<int,int> to get cost of an edge in O(log m) time

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You can sort the adjacency lists for all vertices and then use binary search to achieve O(logN) worst-case :)

→ Reply