Prim's algorithm is a greedy
algorithm that finds a minimum spanning tree for a weighted undirected graph.
This means 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
graphs that are sufficiently dense, Prim's algorithm can be made to run in
linear time, meeting or improving the time bounds for other algorithms.
1. Start at any node in the graph.
Mark the starting node as reached.
Mark all the other nodes in the graph as unreached.
#Minimum cost Spanning Tree
(MST) consists of the starting node.
2. Find an edge e with minimum cost in the graph that connects a reached node x
to an unreached node y.
3. Add the edge e found in the previous step to the MST.
Mark the unreached node y as reached.
4. Repeat the steps 2 and 3 until all nodes in
the graph have become reached.
Pseudo code
ReachSet =
{0};
// You can use any node...
UnReachSet = {1, 2, ..., N-1};
SpanningTree = {};
while ( UnReachSet ≠ empty ) {
Find
edge e = (x, y) such that:
x ∈ ReachSet
y ∈ UnReachSet
e
has smallest cost
SpanningTree = SpanningTree ∪ {e};
ReachSet = ReachSet ∪ {y};
UnReachSet = UnReachSet - {y};
}
Do you know it?
Developed 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.
No comments:
Post a Comment