Detailed explanation of examples of minimum spanning trees-javaTutorial-php.cn

Detailed explanation of examples of minimum spanning trees

零下一度

Release： 2017-06-25 13:30:28

Original

3426 people have browsed it

Minimum Spanning Tree-Prim's Algorithm and Kruskal's Algorithm

The spanning tree of a graph is an acyclic connected subgraph containing all vertices, a weighted graph The minimum spanning tree of is its spanning tree with the smallest weight.

Prim algorithm

Simple description of the algorithm

1). Input: a weighted connected graph, in which the vertex set is V and the edge set is E;

2). Initialization: V_new = {x}, where x is any node (starting point) in the set V, E_new = {}, is empty;

3). Repeat the following Operation until V_new = V:

a. Select the edge with the smallest weight in set E , where u is the set V elements in _new, and v is not in the V_new set, and v∈V (if there are multiple edges that meet the above conditions and have the same weight, you can choose arbitrarily One of them);

b. Add v to the set V_new, and add the edge to the set E_new Medium;

4). Output: Use the set V_new and E_new to describe the resulting minimum spanning tree.

The following is an illustration description of the algorithm

##The next vertex is distanceC, GB, E, FA, DThe algorithm continues to repeat the above steps. Vertex CB, E, GA, D, F##A, D, F, B, EG

Legend	Description	Not optional	Optional	Selected(V_new)
	This is the original weighted connected graph. The number on one side of each edge represents its weight.	-	-	##-
	Vertex D is arbitrarily chosen as the starting point. Vertices A, B, E, and F are connected to D by a single edge. A is the vertex closest to D, so A and the corresponding edge AD are highlighted.	C, G	A, B, E, F	D
	D Or A nearest vertex. B is 9 from D, 7 from A, 15 from E, and 6 from F. Therefore, F is closest to D or A, so the vertex F and the corresponding edge DF are highlighted.
	B with a distance of 7 from A is highlighted.
	In the current situation, you can choose between C, E and G. C is 8 from B, E is 7 from B, and G is 11 from F. E is closest, so the vertex E and the corresponding edge BE are highlighted.	None	C, E, G	A, D, F, B
	##Here, the only vertices to choose from are C and G. The distance between C and E is 5, and the distance between G and E is 9, so C is selected and combined with the edge EC are highlighted together.	None	C, G
#Vertex	is the only remaining vertex, Its distance from F is 11, its distance from E is 9, and E is the closest, so G and the corresponding edge EG are highlighted. None	G	##A, D, F, B, E, C
Now, all the vertices have been selected, and the green part in the picture is is the minimum spanning tree of a connected graph. In this example, the sum of the weights of the minimum spanning tree is 39.	None	None	##A, D, F, B, E, C, G	For algorithm implementation, please refer to the fourth edition of "Algorithm", or "Data Structure - Java Language Implementation" by Tsinghua Publishing House (the implementation method is clearer and simpler) Kruskal Algorithm 1. Overview Kruskal's algorithm is an algorithm used to find the minimum spanning tree, published by Joseph Kruskal in 1956. There are also Prim algorithm and Boruvka algorithm used to solve the same problem. All three algorithms are applications of greedy algorithms. The difference from Boruvka's algorithm is that Kruskal's algorithm is also effective when there are edges with the same weight in the graph. 2. Brief description of the algorithm 1). Remember that there are v vertices and e edges in Graph 2). Create a new graph Graph_new, and Graph_new has the original graph The same e vertices, but no edges 3). Sort all e edges in the original graph Graph from small to large by weight 4). Loop: start from the edge with the smallest weight and traverse each edge until all nodes in the graph are in the same connected component ## If this edge is connected The two nodes in the graph Graphnew_{are not in the same connected component.} Legend description: First of all, we have a graph Graph with several points and edges Sort the lengths of all edges, and use the sorted results as the basis for our edge selection. Here again the idea of greedy algorithm is reflected. Resource sorting selects the locally optimal resources. After the sorting is completed, we take the lead in selecting edge AD. In this way, our picture becomes the picture on the right Look for the remaining changes. We found CE. The weight here is also 5 and so on. We find 6, 7, 7, that is, DF, AB, BE. Continue to select BC or EF although the side with a length of 8 is now the smallest unselected side. But now they are connected (BC can be connected through CE, EB, similar EF can be connected through EB, BA, AD, DF). So no need to select them. Similar BDs are also connected (the connecting lines in the above picture are shown in red). In the end, only EG and FG are left. Of course we chose EG. Algorithm implementation can refer to the code in the fourth edition of "Algorithm".

The above is the detailed content of Detailed explanation of examples of minimum spanning trees. For more information, please follow other related articles on the PHP Chinese website!