446,213 Members | 1,117 Online
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

 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
4 Replies

 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

 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

 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,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