By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,213 Members | 1,117 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,213 IT Pros & Developers. It's quick & easy.

implementing a graph

bucketbot
P: 9
Can anyone explain how to code a graph based on a priority queue? As in, what would I need to do in order to successfully implement a graph? thanks
May 19 '07 #1
Share this Question
Share on Google+
4 Replies


bucketbot
P: 9
Can anyone explain how to code a graph based on a priority queue? As in, what would I need to do in order to successfully implement a graph? thanks
i forgot to mention that the graph needs to be an adjacency list, and that it should be implemented with an ArrayList
May 19 '07 #2

Expert 10K+
P: 11,448
i forgot to mention that the graph needs to be an adjacency list, and that it should be implemented with an ArrayList
I'm sorry, I think I don't understand your question. What have priority queues
to do with graphs? Do you have to build your adjacency matrix yourself or is
that given already? What do you want to do with that graph?

kind regards,

Jos
May 20 '07 #3

bucketbot
P: 9
I'm sorry, I think I don't understand your question. What have priority queues
to do with graphs? Do you have to build your adjacency matrix yourself or is
that given already? What do you want to do with that graph?

kind regards,

Jos

we constructed a min-heap based priority queue, and now we have to design a graph (for use with Dijkstras algorithm) using that PQ. I just don't understand how to construct the graph. So far, I have a Graph class, a Vertex class, and an Edge class. If my vertex class is simply a name and an array of incident edges, then what is my Edge class?

the end product is suppose to be something that reads in input (in this case, a sort of map), and it has to determine which path has the shortest distance or shortest time to travel.

thanks
May 21 '07 #4

prometheuzz
Expert 100+
P: 197
...

I just don't understand how to construct the graph. So far, I have a Graph class, a Vertex class, and an Edge class. If my vertex class is simply a name and an array of incident edges, then what is my Edge class?

...
An Edge class isn't necessary. Just use a java.util.List in your Vertex class that holds references to the neighbouring Vertices.
And your Graph class has a java.util.List with Vertex objects of course.

Another approach is to use an implementation of a java.util.Map<Key, Value>,where the key is a (unique) Vertex and the value is a java.util.List containing the Vertex's neighbours.

Good luck.
May 22 '07 #5

Post your reply

Sign in to post your reply or Sign up for a free account.