Kruskal v. Prim-Jarnik

[Kirby]

I'm doing a project to compare the running times between Kruskal's and Prim-Jarnik algorithms. I'm a little lost on where to start in constructing a graph.

I think I need a priority queue or heap to store the egdes and possibly a linked list to store vertices that I've already gone through. I'm a bit confused of how to store the distance and the vertices in the queue. Would an array of structs that stored the vertices and distances work in a queue, and just order it by the distance? I just don't understand how to get from the graph to the queue.

Also, would it be easier to do an adjacency list or matrix to originally store the graph? An adjacency list would be a list of distances pointing to a list of vertices, correct? How could I read that in easily (file input)?

I know an adjacency matrix would just be a 2d array, but how would I get it to the queue? Same applies for the adj. list.

Sorry for all the ambiguous questions, I was sick for a few days and missed some class, and the book hasn't been too much help in showing how to implement things. I need to do well on this project or I'm going to fail the class.

Any help would be greatly appreciated.

 

[George P Burdell]

This is a good time to find a TA.

 

[Kirby]

No TA, but I'm going to talk to the teacher sometime this week. The project is a bonus, but I made a 45 on the first test and a 88 on the second. We've had one homework and one other project, neither of which we've gotten grades. I could probably pass without the bonus, but it'd sure take a load off my mind.

 

[Kyteland]

If you just need to compare the two algorithms, the Boost Graph Library already does everything you need.

or did the assignment specifically state to implement the graph structures yourself?