Prim algorithm
Prim’s algorithm is an algorithm in graphs that can search for minimum spanning trees in weighted connected graphs.
The function of the algorithm is to find the shortest path connecting all vertices according to the weights in the graph, that is, the sum of the minimum weights connecting all vertices, which is also the minimum spanning tree in the weighted graph.
Prim algorithm steps
1. Select one vertex of the edge with the lowest weight as the starting point. 2. Find the edge with the lowest weight from the current vertex and record that the vertex is selected. 3. Repeat step 2 until all vertices are found and the minimum spanning tree of the graph is found.
Prim algorithm time complexity
Let’s say we have V for the number of vertices in the graph, E for the number of edges in the graph.
In the simple implementation of adjacency matrix graph representation, all minimum weight edge common needs are found
Using simple binary heap and adjacency list, the running time of Prim algorithm can be reduced to
If a more complex Fibonacci heap is used, the running time can be further reduced to
Prim algorithm example
Find the minimum spanning tree based on the weighted connected graph above.
conclusion
Prim algorithm is to find the edge with the least weight through a vertex diffusion, and the vertex and edge passed by are the minimum spanning tree of the graph. The time complexity of storing graphs by different data structures will be inconsistent. The time complexity of using adjacency matrix is
PS: Clear mountains and clear waters begin with dust, knowledge is more valuable than diligence. I got wine. You got a story? Wechat official account: “Clean the dust chat”. Welcome to chat and talk about code.
