I've had a look through your code and it seems like your design is incomplete in some areas. Let's take a look.
Your graph
class looks like this:
class graph {
public:
... function prototypes ...
private:
int numVert;
int numEdges;
};
This class declaration is missing some rather important information: in particular, while the number of vertices and the number of edges is stored, no information about the vertices or edges belonging to a given graph
instance is ever stored.
You already have edge
and city
structs that can be used for edges and vertices respectively. These can be stored in std::vector<...>
members of your graph
class, and - if you are careful to preserve the relevant orderings - you can address these by numerical index and be (mostly) fine. Once you've done that, you can tweak addEdge
and addCity
such that they actually do what they should - that is, add a edge or a vertex, respectively, to the graph
instance.
Another thing to think about is how you actually want to store your edges. The 'best' approach depends on the nature of the problem, but for most applications, it suffices to store edges either in a structure keyed by vertex ID (e.g. a std::map<std::vector<...> >
instance), or as a subfield in each vertex object (e.g. by adding a std::vector<...>
member field to your city
class).
This aside, let's address the actual algorithm you're trying to implement.
Prim's algorithm is, at its heart, iterated application of this rule:
Add to the candidate minimum spanning tree the minimal-weight edge connecting some vertex inside the tree to some vertex outside.
That is, at each step, we do this:
- Consider the vertices in the tree we have built up so far; call this set A. (At the very beginning, this is a single vertex of your choice. At the end, this is the vertex set of the connected component containing the initial vertex; if your graph is connected, this is all the vertices.)
- Consider the vertices in our graph that are not in the tree; call this set B.
- Look at all possible edges connecting any vertex in set A with any vertex in set B (in graph-theory language. the cut-set of the cut (A, B) of your graph). If there are none, you're done. Otherwise, pick the edge among these with the smallest weight and add it to the tree.
You can prove that, given that the original graph is connected, this algorithm produces a spanning tree with minimal total edge weight. Try to justify this to yourself.
So, where are you right now? While I can't read your mind, I can tell you what your code is telling me:
- You're trying to keep track of the set of vertices you've already visited.
- This is good; you'll need that.
- You're trying to keep track of the cut-set, i.e. the edges exiting the visited set.
- You'll need this as well.
- I'm not sure why you're using only a
std::vector<unsigned int>
for this purpose, since for a given edge you need to track three quantities: the 'from' vertex, the 'to' vertex, and the weight. You might want astd::vector<edge>
instead for this purpose.
- It looks like you're trying to populate this set.
- You may need to redo this bit, depending on whether you change the layout of your data structures.
- The main idea - find edges running from visited nodes to unvisited nodes - is there, but I'm not sure the approach the current code is suggesting is going to work.
So, what's missing from the algorithm?
- Once you have a valid cut-set, you need to find the edge in the set with the lowest weight.
- You need to add this edge to the return set.
- You need to mark the vertex this edge connects to as visited. Call this node N.
- You need to update the cut-set. In particular, any edges connecting N to the vertices previously visited need to be removed, and any edges connecting N to some unvisited vertex need to be added.
I hope this helps you out. If you're confused about anything, need some more explanation, or think something I've said is inaccurate or incorrect, let me know and I'll update this answer.