LinuxAnswers - the LQ Linux tutorial section.
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org C++ graph / map data structure
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 10-17-2010, 09:38 AM #1 Galib Member   Registered: Mar 2009 Location: \$HOME Distribution: Slackware64 Posts: 69 Rep: C++ graph / map data structure I am having a little trouble understanding the graph data structure. If you guys know any links that provide sample code that I can look at and learn please help! Just need some help getting the ball rolling on an assignment that requires me to find the most efficient route from a city to another city. I've thought about the algorithm (using a stack & recursion) but I need help to as how I store the cities. For basics, I made an array that holds each city (no duplitcates). So, cities[] has from 0 to 4: A B C D E. How to I approach creating the links, such as A as links to B & E, C has a link to B. I did some reading and ran into creating an adjacentMatrix ( ? ) or vector (?) ? This is where I am stuck!
 10-17-2010, 10:13 AM #2 dugan Guru   Registered: Nov 2003 Location: Canada Distribution: distro hopper Posts: 5,294 Rep: Your course textbook didn't mention these? http://en.wikipedia.org/wiki/Adjacency_matrix http://en.wikipedia.org/wiki/Adjacency_list
 10-17-2010, 10:34 AM #3 Galib Member   Registered: Mar 2009 Location: \$HOME Distribution: Slackware64 Posts: 69 Original Poster Rep: It actually didn't. The book is terrible, I was looking for a better book and ran into reviews, this had like 2 stars tops out of 5! I read through the two links you gave, it reminds me of trees (although we haven't covered that in this class). I am guessing the adjacent array would be a two dimensional array, adj [] []. Thanks
 10-17-2010, 08:50 PM #4 graemef Senior Member   Registered: Nov 2005 Location: Hanoi Distribution: Fedora 13, Ubuntu 10.04 Posts: 2,379 Rep: Yes you will want a two dimensional array of integers. The dimensions will be n x n where n equals the number of cities and the value will be cost of travelling from one city to the other. If the costs are uniform (i.e the cost of travelling from A to B is the same as travelling from, B to A) then the matrix will be symmetrical.