Minimal Spanning Tree¶
Spanning Tree¶
A spanning tree of a graph is a subgraph that contains all vertices of the graph and is a tree. A tree is a connected graph with no cycles.
A graph can have multiple spanning trees.
Both DFS and BFS can be used to find a spanning tree of a graph.
Minimal Spanning Tree¶
A Minimum Spanning Tree (MST) is a subgraph of a weighted, connected graph that spans all vertices with the minimum possible total edge weight. MSTs have various practical applications in network design, clustering, and more.
Prim’s Algorithm
Kruskal’s Algorithm
Other
Boruvka’s Algorithm
Reverse-Delete Algorithm
Visualization
Prim’s Algorithm¶
Prim’s algorithm is a greedy algorithm used to find the Minimum Spanning Tree of a graph. It starts with an arbitrary vertex and repeatedly adds the shortest edge that connects a vertex in the MST to a vertex outside the MST.
invented by Czech mathematician Vojtěch Jarník in 1930
rediscovered and republished by computer scientists Robert C. Prim in 1957 and Edsger W. Dijkstra in 1959
use a priority queue to keep track of the vertices and their weights
store the MST in a separate data structure
Algorithm Steps¶
Create an empty MST.
Initialize a priority queue with all vertices and their respective weights.
Start with an arbitrary vertex as the current vertex.
Mark the current vertex as visited.
While the priority queue is not empty:
Dequeue the vertex with the smallest weight from the priority queue.
If the dequeued vertex is not in the MST, add it to the MST and update its neighbors’ weights in the priority queue.
Repeat steps 4-5 until all vertices are in the MST.
Pseudo-code for Prim’s Algorithm¶
function prim(graph):
create an empty MST
create a priority queue with vertices and their weights
start with an arbitrary vertex as the current vertex
mark the current vertex as visited
while the priority queue is not empty:
dequeue the vertex with the smallest weight from the priority queue
if the dequeued vertex is not in the MST:
add it to the MST
update the weights of its neighbors in the priority queue
Kruskal’s Algorithm¶
Kruskal’s algorithm is another greedy algorithm used to find the Minimum Spanning Tree of a graph. It starts with an empty set of edges and repeatedly adds the shortest edge that does not form a cycle with the edges already selected.
invented by Joseph Kruskal in 1956
use a disjoint-set data structure to keep track of connected components to avoid cycles
Algorithm Steps¶
Create an empty MST.
Sort all edges in the graph in ascending order of their weights.
Initialize a disjoint-set data structure to keep track of connected components.
For each edge in sorted order:
If adding the edge to the MST does not create a cycle, add it to the MST.
Repeat step 4 until the MST has (n-1) edges, where n is the number of vertices in the graph.
Pseudo-code for Kruskal’s Algorithm¶
function kruskal(graph):
create an empty MST
sort all edges in the graph in ascending order of their weights
initialize a disjoint-set data structure
for each edge in sorted order:
if adding the edge to the MST does not create a cycle:
add it to the MST
update the disjoint-set data structure
Comparison of Prim’s and Kruskal’s Algorithms¶
Comparison Criteria |
Prim’s Algorithm |
Kruskal’s Algorithm |
Type |
Greedy |
Greedy |
Graph elements |
Vertices |
Edges |
Efficient for |
Dense graphs |
Sparse graphs |
Data structure/ADT |
Priority queue |
Disjoint-set |
Parallelization |
Not suitable |
Suitable |
Connected results |
Yes |
Yes (extra step) |
Overall Considerations¶
Prim’s Algorithm:
Well-suited for dense graphs and highly connected graphs.
More efficient when a priority queue can be efficiently implemented.
Kruskal’s Algorithm:
Well-suited for sparse graphs and graphs with multiple disconnected components.
Suitable for parallel and distributed computing environments.