LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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

Reply
 
Search this Thread
Old 10-17-2010, 09:38 AM   #1
Galib
Member
 
Registered: Mar 2009
Location: $HOME
Distribution: Slackware64
Posts: 69

Rep: Reputation: 17
Red face 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!
 
Old 10-17-2010, 10:13 AM   #2
dugan
Senior Member
 
Registered: Nov 2003
Location: Canada
Distribution: distro hopper
Posts: 4,765

Rep: Reputation: 1467Reputation: 1467Reputation: 1467Reputation: 1467Reputation: 1467Reputation: 1467Reputation: 1467Reputation: 1467Reputation: 1467Reputation: 1467
Your course textbook didn't mention these?

http://en.wikipedia.org/wiki/Adjacency_matrix
http://en.wikipedia.org/wiki/Adjacency_list
 
Old 10-17-2010, 10:34 AM   #3
Galib
Member
 
Registered: Mar 2009
Location: $HOME
Distribution: Slackware64
Posts: 69

Original Poster
Rep: Reputation: 17
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
 
Old 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: Reputation: 148Reputation: 148
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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
pnp4nagios - getting both IN and OUT data onto 1 graph technobudha Linux - Server 1 06-10-2011 05:16 AM
tcpdump and map graph nawuza Linux - Networking 5 09-21-2008 11:35 PM
Graph data structure generation options and parametrization hamtavs Programming 1 04-18-2008 03:44 PM
LXer: Putting physical data on a Web graph LXer Syndicated Linux News 0 04-28-2006 08:21 PM
gprof: gmon.out file is missing call-graph data hemk76 Programming 0 01-07-2005 11:54 PM


All times are GMT -5. The time now is 04:49 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration