Prim's Minimum Spanning Tree - kgleong/software-engineering GitHub Wiki
- Connected graph
- Edges may have variable weights
Construct a tree that connects all vertices in a graph and optimize for the smallest total edge weight.
The result is known as a Minimum Spanning Tree (MST)
Prim's utilizes a greedy approach to find the MST.
It partitions the graph into two sets:
- Vertices that are in the MST.
- Vertices that are have not been added to the MST yet.
As it discovers new vertices, they are added to the latter set.
Prim's is a greedy algorithm in the sense that it looks at the two vertex sets and finds the edge with minimum weight between the two sets and moves the connected vertex over from the set of vertices outside the MST to the set containing all vertices in the MST.
Since this is a connected graph, there must be an edge from the first set to the second.
The algorithm is repeated until all the vertices have been moved from the second set to the first.
An MST can be represented by a set of edges, where the tree root is the only vertex without a parent.
public Set<Edge> MST(Vertex root) {
// An MST can be represented by a set of edges
Set<Edge> mstEdgeList = new HashSet<>();
// Partition the graph into two set of vertices:
// 1. Those vertices that have been added to the MST.
// 2. Those vertices not in the MST yet.
Set<Vertex> addedList = new HashSet<>();
Set<Vertex> notAddedList = new HashSet<>();
// Add the root to the MST
addedList.add(root);
// Add all vertices adjacent to the root to the not added list
for(Vertex neighbor : root.adjacencyList) {
notAddedList.add(neighbor);
}
// Continue until all vertices have been added to the MST.
while(!notAddedList.isEmpty()) {
Edge minimumEdgeBetweenVertexSets = null;
for(Vertex vertexInMST : addedList) {
for(Edge edge : vertexInMST.adjacencyList) {
// Only look at edges that connect vertices in the MST
// to edges outside the MST.
if(notAddedList.contains(edge.destinationVertex)) {
if(minimumEdgeBetweenVertexSets == null) {
minimumEdgeBetweenVertexSets = edge;
}
else {
// New minimum weight edge
if(minimumEdgeBetweenVertexSets.compare(edge) > 0) {
minimumEdgeBetweenVertexSets = edge;
}
}
}
}
}
// Add the edge to the MST. This effectively moves the destination
// vertex for this edge into the MST.
mstEdgeList.add(minimumEdgeBetweenVertexSets);
// Move the destination vertex into the MST and remove it
// from the list of vertices outside of the MST.
addedList.add(minimumEdgeBetweenVertexSets.destinationVertex);
notAddedList.remove(minimumEdgeBetweenVertexSets.destinationVertex);
}
return mstEdgeList;
}
public class Vertex {
public List<Edge> adjacencyList;
}
public class Edge implements Comparable {
public Vertex sourceVertex;
public Vertex destinationVertex;
int weight;
public int compare(Edge other) {
return weight - other.weight;
}
}