Shulou(Shulou.com)06/03 Report--

This article mainly explains the "example explanation of Prim algorithm in Python". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "Prim algorithm example explanation in Python".

The Prim algorithm of minimum spanning tree is also a classical application of greedy algorithm. The characteristic of Prim algorithm is to maintain a tree all the time. The algorithm keeps adding edges, and the process of adding is always a tree.

Prim algorithm process:

Add one by one to maintain a tree.

Initial E = {} empty collection, V = {optional start node}

Loop (n-1) times, each time select an edge (v1Magne v2), satisfying: v1 belongs to V, v2 does not belong to V. And (v1 ~ (2)) has the least weight.

E = E + (v1pm v2)

V = V + v2

Finally, the edge in E is a minimum spanning tree, and V contains all the nodes.

The following figure shows the execution of the Prim algorithm as an example.

The process of Prim algorithm starts with A, V = {A}, E = {}

Select the edge AF, V = {AmenF}, E = {(AmenF)}

Select the edge FB, V = {Ameno F, B}, E = {(Ameno F), (Freco B)}

Select the edge BD, V = {A, B, F, D}, E = {(A ~ Magi F), (F ~ B), (B ~ D)}

Select edges DE, V = {A, B, F, D ~ E}, E = {(A ~ F), (F ~ B), (B ~ ~ D), (D ~ ~ E)}

Select the edge BC, V = {A, B, F, D ~ E, c}, E = {(A ~ F), (F ~ B), (B ~ ~ D), (D ~ ~ E), (B ~ ~ C)}, and the algorithm ends.

The proof of Prim algorithm: suppose Prim algorithm gets a tree P and a minimum spanning tree T. Assuming that P is different from T, we assume that the edges selected by the Prim algorithm to step (K-1) are all in T, then the tree of the Prim algorithm is paired, and in the K step, the Prim algorithm chooses an edge e = (u, v) is not in T. Suppose u is in P' and v is not.

Because T is a tree, there must be a path from u to v in T. We consider that the first point u in this path is in P', and the last point v is not in P', then there must be an edge on the path f = (x) y), x is in P', and y is not in P'.

We consider the relationship between the edge weights w (f) and w (e) of f and e: if w (f) > w (e), replace f with e in T (add e to T and remove f), get a weight and a smaller spanning tree, which contradicts that T is the minimum spanning tree.

If w (f) < w (e), the Prim algorithm should consider adding f instead of e in the K step, which is a contradiction.

So only w (f) = w (e), we replace f with e in T, so that the edge selected by Prim algorithm in the first K step is in T, and after finite steps T is changed to P, while the tree weight sum is unchanged, so the Prim algorithm is correct.

Please understand the Prim algorithm carefully-- maintain a spanning tree at all times. Our proof constructively proves that all minimum spanning tree edge weights (multiple) sets are the same!

An undirected connected graph with N vertices and M edges, each edge has a weight, and the minimum spanning tree of the graph is obtained.

Finally, we will provide the input and output data, and it is up to you to write a program to implement this algorithm. only when you write the correct program can you continue the following lessons.

Input

Line 1: two numbers N _ M is separated by a space, N is the number of points and M is the number of edges. (2)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.