Storing Adjacency List with Edge Weight

Revision en1, by ben_dover, 2020-02-23 05:03:46

For storing an adjacency list with edge weights, the (apparently) standard way is to store a vector of vector of pairs (vertex end, weight). I realized recently that it is possible to store the adjacency list as for an unweighted graph and store the edge weights separately (in a map or unordered map). noedne pointed out that storing the weight in the adjacency list is more organized. In theory by storing the edge weights separately we can reuse algorithms for unweighted graphs that take the unweighted adjacency list.

Which do you think is better?

Tags data structure, adjacency list, weighted graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ben_dover 2020-02-23 05:03:46 614 Initial revision (published)