Can we use Map of Map for storing weighted graph?

Правка en1, от trunghieu11, 2015-10-06 13:07:46

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?

Теги weighted graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский trunghieu11 2015-10-06 13:07:46 515 Initial revision (published)