4 Replies - 380 Views - Last Post: 03 October 2012 - 06:18 AM Rate Topic: -----

Poll: Best (if applicable) Graph Representation (2 member(s) have cast votes)

What would be the best graph representation for graphs with many edges and vertices?

  1. Edge List Structure (0 votes [0.00%])

    Percentage of vote: 0.00%

  2. Adjacency List Structure (2 votes [100.00%] - View)

    Percentage of vote: 100.00%

  3. Adjacency Matrix Structure (0 votes [0.00%])

    Percentage of vote: 0.00%

Vote Guests cannot vote

#1 xriBit  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-October 12

Poll: Graph implementation of a Simple Map Software

Posted 02 October 2012 - 04:54 PM

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. :dozingoff:

Any HELP will be appreciated. Thanks.

Is This A Good Question/Topic? 0
  • +

Replies To: Poll: Graph implementation of a Simple Map Software

#2 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1152
  • View blog
  • Posts: 2,530
  • Joined: 05-May 05

Re: Poll: Graph implementation of a Simple Map Software

Posted 02 October 2012 - 07:26 PM

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

Was This Post Helpful? 2
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10442
  • View blog
  • Posts: 38,677
  • Joined: 27-December 08

Re: Poll: Graph implementation of a Simple Map Software

Posted 03 October 2012 - 05:41 AM

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.
Was This Post Helpful? 1
  • +
  • -

#4 xriBit  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-October 12

Re: Poll: Graph implementation of a Simple Map Software

Posted 03 October 2012 - 06:17 AM


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



Google Maps is my motivation. This is for a school project I'm working with for our Data Structures course.

Thank you Mr. macosxnerd101 . I'll be checking out your tutorials. :)
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10442
  • View blog
  • Posts: 38,677
  • Joined: 27-December 08

Re: Poll: Graph implementation of a Simple Map Software

Posted 03 October 2012 - 06:18 AM

Glad I could help! :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1