Please enable JavaScript.
Coggle requires JavaScript to display documents.
Prim's Algorithm - Coggle Diagram
Prim's Algorithm
"given n points, connect them in the cheapest possible way so that there will be a path between every pair of points."
the cheapest way to achieve connectivity
This question can be posed as the minimum spanning tree problem:
"A spanning tree of an undirected connected graph is its connected acyclic subgraph (i.e., a tree) that contains all the vertices of the graph"
Weighted Graphs:
A
minimum spanning tree
is its spannig tree of the smallest weight, where the weight of a tree is defined as the sum of the weights on all its edges.
Prim’s
algorithm
If we were to try constructing a minimum spanning tree by exhaustive search,
we would face two serious obstacles:
the number of spanning trees grows
exponentially with the graph size
generating all spanning trees for a given graph is not easy
Constructs a minimum spanning tree through a sequence
of expanding subtrees.
initial subtree:
a single vertex selected arbitrarily from the set V of the graph’s vertices.
On each iteration, the algorithm expands the current tree in the greedy manner by simply attatching to it the nearest vertex not in that tree
The algorithm stops after all the graph’s vertices have
been included in the tree being constructed
Total number of such iterations is
n − 1
, where n is the number of vertices in the graph
Algorithm Efficiency:
Depends on the data structures
chosen for the graph itself and for the priority queue
In Particular...
Graph:
weight matrix
Adjacency List
Priority Queue:
unordered array
The algorithm’s running time will be in BigTheta (|V|^2).
min-heap
The running time of the algorithm is in BigO(|E| log |V |)