In the Graph Theory, Prim’s algorithm creates an optimal spanning tree. I will show here my implementation of this algorithm. It is used in the Graph Lib that I showed you earlier. I don’t pretend that it is done the best way, but it’s working completely.
1 2 3 4 5 6 7 |
OGraph tree = new OGraph(); ArrayList vertices = new ArrayList(this.graph.Vertices.Count); vertices.AddRange(this.graph.Vertices.ToArray()); ArrayList edges = new ArrayList(this.graph.Edges.Count); edges.AddRange(this.graph.Edges.ToArray()); |
We create a copy of our vertices & edges because we are going to manipulate this collections and we do not want this to affected our graph. Well, let’s begin constructing our optimal spanning tree. We need a root vertex for this tree and I am going to use the first vertex in the collection. Remove it and add it to the tree.
1 2 |
tree.Vertices.Add((int)vertices[0]); vertices.RemoveAt(0); |
We are performing next steps until out collection of vertices is empty.
1 |
while (vertices.Count > 0) |
In every loop we have to find an optimal edge with one vertex in the tree vertices and other in the vertices collection. When we find it (and we must find it!) we add this edge and the vertex (which was not in the tree vertices collection) to the tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
Edge optEdge = null; foreach (Edge e in edges) { if ((vertices.Contains(e.Source) && !vertices.Contains(e.Target)) || (vertices.Contains(e.Target) && !vertices.Contains(e.Source))) { if (optEdge == null || (optimalType == OGraph.OptimalType.Minimum && e.CompareTo(optEdge) > 0) || (optimalType == OGraph.OptimalType.Maximum && e.CompareTo(optEdge) > 0)) { optEdge = e; } } } int vertex = vertices.Contains(optEdge.Source) ? optEdge.Source : optEdge.Target; vertices.Remove(vertex); tree.Vertices.Add(vertex); edges.Remove(optEdge); tree.Edges.Add(optEdge); |
So, that’s it! We have an optimal (max or min) spanning tree, constructed using the Prim’s algorithm. I have shown an example in my post for the Graph Lib. If you have any recommendations about this implementation, feel free to say them.