Algorithms
Prim’s Algorithm
Definition
Link to originalPrim's Algorithm
Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected network. It builds the tree one vertex at a time, starting from an arbitrary root vertex, at each step adding the cheapest possible connection from the tree to another vertex.
For dense graphs, where , Prim’s algorithm typically performs better than Kruskal’s algorithm.
Kruskal’s Algorithm
Definition
Link to originalKruskal's Algorithm
Kruskal’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected network. It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
For sparse graphs, where , Kruskal’s algorithm typically performs better than Prim’s algorithm.