CODEWITHSUNDEEP
algorithmdata-structuresgraph
StonerLoods
StonerLoods

Reputation: 121

Adjacency matrix vs adjacency list for directed weighted graph

As an exercise I have to build a satnav system which plans the shortest and fastest routes from location to location. It has to be as fast as I can possibly make it without using too much memory.

I am having trouble deciding which structure to use to represent the graph. I understand that a matrix is better for dense graphs and that a list would be better for sparse graphs. I'm leaning more towards using a list as I'm assuming that adding vertexes will be the most taxing part of this program.

I just want get some of your guys' opinions. If I were to look at a typical road-map as a graph with various locations being nodes and the roads being edges. Would you consider it to be sparse or dense? Which structure seems better in this scenario?

Upvotes: 3

Views: 602

Answers (1)

Sumeet
Sumeet

Reputation: 8292

I would go for lists because its only 1 time investment. The good thing about it is that it is able to iterate over all the adjacent vertices faster than matrix which is an important and most frequent steps in most of the shortest path algorithms.

So where matrix is O(N) adjacency list goes only O(k) where k is number of adjacent vertices.

Upvotes: 3

Related Questions