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

This article introduces the relevant knowledge of "Java how to implement minimum spanning tree MST". In the actual case operation process, many people will encounter such difficulties. Next, let Xiaobian lead you to learn how to deal with these situations! I hope you can read carefully and learn something!

Simple explanation

When defining a graph, we define that the spanning tree of a connected graph is a minimal connected subgraph with N vertices and N-1 edges.

Prim algorithm Prim algorithm is suitable for dense graphs, its time complexity is O(n ^2), its time complexity is independent of the number of edges, and the weight value is considered by finding the vertex by vertex.

Storage method is adjacency matrix

Basic idea: Suppose G=(V, E) is connected and TE is the set of edges in the minimal spanning tree on G. The algorithm starts with U={u0}(u0∈V), TE={}. Repeat the following:

Among all edges (u, v)∈E of u∈U, v∈V-U, find an edge (u0,v0) with the smallest weight and merge it into TE, at the same time, v0 merges into U until V=U.

In this case, TE must have n-1 edges, T=(V, TE) is the minimum spanning tree of G.

The core of Prim algorithm: always keep the edge set in TE to form a spanning tree.

Note: prim algorithm is suitable for dense graphs, its time complexity is O(n^2), its time complexity is independent of the number of edges,

To better understand, let's take an example here:

(1) There are 6 vertices v1-v6 in the graph, and the edge weights of each edge are on the graph; when performing the prim algorithm, I first choose a vertex as the starting point. Of course, we usually choose v1 as the starting point. Okay, now let us set the U set as the vertices in the minimum spanning tree currently found, and the TE set as the edges found. The state is as follows:

U={v1}; TE={};

(2) Now find the minimum weight of one vertex in the U set and another vertex in the V-U set, as shown below, find the minimum value on the line where the red lines intersect.

From the graph we can see that the edge v1-v3 has a weight of at least 1, so adding v3 to the U set,(v1, v3) to TE, the state is as follows:

U={v1，v3}; TE={（v1，v3）};

(3) Continue searching, the state is now U={v1, v3}; TE={(v1, v3)}; find the minimum value on the edge intersecting the red line.

We can find the smallest weight (v3, v6)=4, then we add v6 to the U set and the smallest edge to the TE set, then the state after adding is as follows:

U={v1, v3, v6}; TE={(v1, v3),(v3, v6)}; and so on until all vertices are found.

(4) The following image shows us the whole search process:

#include#includeusing namespace std;#define MAX 100#define MAXCOST 65535int graph[MAX][MAX];int Prim(int graph[][MAX], int m)//m is the number of points { int lowcost[m]; int mst[m]; int i, j, min, k, sum = 0; mst[1] = 0; lowcost[1]=0; for (i = 2; i

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.