Prim's algorithm

Graph and tree search algorithms
α–β A* B* Beam Bellman–Ford Best-first Bidirectional Borůvka Branch & bound BFS British Museum D* DFS Depth-limited Dijkstra Edmonds Floyd–Warshall Hill climbing Iterative deepening Kruskal Johnson Lexicographic BFS Prim Uniform-cost
Listings
Graph algorithms Search algorithms List of graph algorithms
Related topics
Dynamic programming Graph traversal Tree traversal Search games

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected 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. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is also sometimes called the DJP algorithm, the Jarník algorithm, or the Prim–Jarník algorithm.

Other algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm. However, these other algorithms can also find minimum spanning forests of disconnected graphs, while Prim's algorithm requires the graph to be connected.

1 Description
- 1.1 Informal
- 1.2 Technical
2 Time complexity
3 Example run
4 Proof of correctness
5 References
6 External links

Description

Informal

create a tree containing a single vertex, chosen arbitrarily from the graph
create a set containing all the edges in the graph
loop until every edge in the set connects two vertices in the tree
- remove from the set an edge with minimum weight that connects a vertex in the tree with a vertex not in the tree
- add that edge to the tree

Technical

Prim's algorithm has many applications, such as in the generation of this maze, which applies Prim's algorithm to a randomly weighted grid graph.

If a graph is empty then we are done immediately. Thus, we assume otherwise.

The algorithm starts with a tree consisting of a single vertex, and continuously increases its size one edge at a time, until it spans all vertices.

Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative).
Initialize: V_new = {x}, where x is an arbitrary node (starting point) from V, E_new = {}
Repeat until V_new = V:
- Choose an edge {u, v} with minimal weight such that u is in V_new and v is not (if there are multiple edges with the same weight, any of them may be picked)
- Add v to V_new, and {u, v} to E_new
Output: V_new and E_new describe a minimal spanning tree

Time complexity

Minimum edge weight data structure	Time complexity (total)
adjacency matrix, searching	O(V²)
binary heap and adjacency list	O((V + E) log V) = O(E log V)
Fibonacci heap and adjacency list	O(E + V log V)

A simple implementation using an adjacency matrix graph representation and searching an array of weights to find the minimum weight edge to add requires O(V²) running time. Using a simple binary heap data structure and an adjacency list representation, Prim's algorithm can be shown to run in time O(E log V) where E is the number of edges and V is the number of vertices. Using a more sophisticated Fibonacci heap, this can be brought down to O(E + V log V), which is asymptotically faster when the graph is dense enough that E is ω(V).

Example run

U	possible edges	V \ U	Description
{}		{A,B,C,D,E,F,G}	This is our original weighted graph. The numbers near the edges indicate their weight.
{D}	{D,A} = 5 V {D,B} = 9 {D,E} = 15 {D,F} = 6	{A,B,C,E,F,G}	Vertex D has been arbitrarily chosen as a starting point. Vertices A, B, E and F are connected to D through a single edge. A is the vertex nearest to D and will be chosen as the second vertex along with the edge AD.
{A,D}	{D,B} = 9 {D,E} = 15 {D,F} = 6 V {A,B} = 7	{B,C,E,F,G}	The next vertex chosen is the vertex nearest to either D or A. B is 9 away from D and 7 away from A, E is 15, and F is 6. F is the smallest distance away, so we highlight the vertex F and the edge DF.
{A,D,F}	{D,B} = 9 {D,E} = 15 {A,B} = 7 V {F,E} = 8 {F,G} = 11	{B,C,E,G}	The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted.
{A,B,D,F}	{B,C} = 8 {B,E} = 7 V {D,B} = 9 cycle {D,E} = 15 {F,E} = 8 {F,G} = 11	{C,E,G}	In this case, we can choose between C, E, and G. C is 8 away from B, E is 7 away from B, and G is 11 away from F. E is nearest, so we highlight the vertex E and the edge BE.
{A,B,D,E,F}	{B,C} = 8 {D,B} = 9 cycle {D,E} = 15 cycle {E,C} = 5 V {E,G} = 9 {F,E} = 8 cycle {F,G} = 11	{C,G}	Here, the only vertices available are C and G. C is 5 away from E, and G is 9 away from E. C is chosen, so it is highlighted along with the edge EC.
{A,B,C,D,E,F}	{B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {E,G} = 9 V {F,E} = 8 cycle {F,G} = 11	{G}	Vertex G is the only remaining vertex. It is 11 away from F, and 9 away from E. E is nearer, so we highlight G and the edge EG.
{A,B,C,D,E,F,G}	{B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {F,E} = 8 cycle {F,G} = 11 cycle	{}	Now all the vertices have been selected and the minimum spanning tree is shown in green. In this case, it has weight 39.

This animation shows how Prim's algorithm runs in a graph.(Click the image to see the animation)

Proof of correctness

Let P be a connected, weighted graph. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since P is connected, there will always be a path to every vertex. The output Y of Prim's algorithm is a tree, because the edge and vertex added to tree Y are connected. Let Y₁ be a minimum spanning tree of graph P. If Y₁=Y then Y is a minimum spanning tree. Otherwise, let e be the first edge added during the construction of tree Y that is not in tree Y₁, and V be the set of vertices connected by the edges added before edge e. Then one endpoint of edge e is in set V and the other is not. Since tree Y₁ is a spanning tree of graph P, there is a path in tree Y₁ joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in set V to one that is not in set V. Now, at the iteration when edge e was added to tree Y, edge f could also have been added and it would be added instead of edge e if its weight was less than e (we know we encountered the opportunity to take "f" before "e" because "f" is connected to V, and we visited every vertex of V before the vertex to which we connected "e" ["e" is connected to the last vertex we visited in V]). Since edge f was not added, we conclude that

$w(f) \ge w(e).$

Let tree Y₂ be the graph obtained by removing edge f from and adding edge e to tree Y₁. It is easy to show that tree Y₂ is connected, has the same number of edges as tree Y₁, and the total weights of its edges is not larger than that of tree Y₁, therefore it is also a minimum spanning tree of graph P and it contains edge e and all the edges added before it during the construction of set V. Repeat the steps above and we will eventually obtain a minimum spanning tree of graph P that is identical to tree Y. This shows Y is a minimum spanning tree.

References

V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57–63. (in Czech)
R. C. Prim: Shortest connection networks and some generalizations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
D. Cheriton and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal on Computing, 5 (Dec. 1976), pp. 724–741
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press, 2009. ISBN 0-262-03384-4. Section 23.2: The algorithms of Kruskal and Prim, pp. 631–638.

External links

fonte: https://web.archive.org/web/20120916001027/https://en.wikipedia.org/wiki/Prim%27s_algorithm

Conheça Walt Disney World