# Poll: Graph implementation of a Simple Map Software

Page 1 of 1

## 4 Replies - 516 Views - Last Post: 03 October 2012 - 06:18 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=294016&amp;s=67dcfc8b811a5ca309e0c990c73f211f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### 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%

Percentage of vote: 100.00%

Percentage of vote: 0.00%

Vote Guests cannot vote

### #1 xriBit

Reputation: 0
• 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.

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

• D.I.C Lover

Reputation: 1158
• Posts: 2,538
• 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

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,173
• 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.

### #4 xriBit

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

## Re: Poll: Graph implementation of a Simple Map Software

Posted 03 October 2012 - 06:17 AM

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.

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11449
• Posts: 43,173
• Joined: 27-December 08

## Re: Poll: Graph implementation of a Simple Map Software

Posted 03 October 2012 - 06:18 AM

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }