LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   C++ graph / map data structure (https://www.linuxquestions.org/questions/programming-9/c-graph-map-data-structure-838634/)

Galib 10-17-2010 09:38 AM

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!

dugan 10-17-2010 10:13 AM

Your course textbook didn't mention these?

http://en.wikipedia.org/wiki/Adjacency_matrix
http://en.wikipedia.org/wiki/Adjacency_list

Galib 10-17-2010 10:34 AM

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

graemef 10-17-2010 08:50 PM

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.


All times are GMT -5. The time now is 07:57 PM.