[xriBit]

I'm about to start a project. This will be a Simple Map Software that shows the map of our campus with a pathfinder that will plot shortest path. I've looked through useful data structures and eventually found Graph ADT. I'm stucked in choosing which is the best representation for the graph, is an "Edge List Structure", "Adjacency List Structure", or "Adjacency Matrix Structure"? Since the vertices will be places in our campus (e.g. canteen, library) and this will be many.

Plus, can you provide a walkthrough on how will a simple map be? im really confused.

Any HELP will be appreciated. Thanks.

[blackcompe]

Adjacency matrices are out of the question since they are O(n^2) in space. Furthermore, a considerable number of elements may be empty. Adjacency lists are O(m+n) in space. There are trade-offs between the two, but I'd say lists are usually the better choice. It depends on what you're doing. If you needed to quickly test whether two nodes are neighbors, it's constant time with a matrix, but if you're going to be traversing the graph, where you're using depth-first search (Dijkstra's), you have to traverse all n^2 entries in the matrix (even if its sparse), which is costly compared to an adjacency list. I've never used edge lists, so I can't tell you about them.

This post has been edited by blackcompe: 02 October 2012 - 07:27 PM

[macosxnerd101]

I find it easier to implement pathfinding algorithms with an adjacency list model over an adjacency matrix model. It isn't as difficult to organize the data to track previous and future visits. With adjacency matrices, the parallel arrays model is hard to deal with. I would use adjacency matrices when counting paths from a to b. I wrote a tutorial on representing graphs that you may find helpful.

Also, you might consider just using Google Maps instead of rolling your own implementation.

[xriBit]

Also, you might consider just using Google Maps instead of rolling your own implementation.

[macosxnerd101]

Glad I could help!