This problem has been investigated in Examples 1 - 2 and 1 - 3. Because each spanning of the non-terminalless network G of the N top points is just the N-1 strip, the problem is to select the N-1 strip while selecting the minimum tree of G. At least three different greedy strategies can be used to select this N-1. These three greedy algorithms strategies for the minimum spanning tree are: K R u s k a L algorithm, P R I m algorithm and S O L i n algorithm.
Kruskal algorithm
(1) Algorithm thinking
K r u s k a l algorithm selection N- 1 edge, the greedy criterion used is: Select a collection of minimum spending from the remaining edge to add a collection of selected edges. Note that if the selected edge is generated, it is impossible to form a spanning tree. K R u s k a L calculated E step, where E is the number of the network. Considering this E strip according to the incremental order, each time considering a side. When considering a certain strip, the loop will appear in the collection of the selected border, then discard it, otherwise it is selected.
Investigate the network in Figure 1-12A. There is no side when it is initially selected. Figures 13-12b show the current state of each node. Side (1, 6) is the first side of the first first, it is added to the spanning tree to build, resulting in Figure 1 3 - 1 2 C. The next step is selected (3, 4) and add it into the tree (as shown in Figure 1 3 - 1 2 D). Then consider the edges (2, 7), adding it into the tree and does not generate loops, so it is obtained by Figure 1 3 - 1 2 E. Next step (2, 3) and add it into the tree (as shown in Figure 1 3 - 1 2 F). In the remaining side, (7, 4) has a minimum consumption, so first consider it, add it to the tree that is being created, will generate loops, so discard it. Thereafter, the side (5, 4) is added to the tree, and the obtained tree is shown in Figure 13-12g. Next step (7, 5), due to the loop, it will be discarded. Finally, consider the edges (6, 5) and add it into the tree, producing a spanning tree, which costs 9 9. Figure 1 - 1 3 shows the pseudo code of the K R U S K A L algorithm.
/ / Find a minimum span tree in a network with N top points
Let T are the collection of the selected borders, initialization T =
Let E give a collection in the network
W h i l e (e) && (| t | ≠ n- 1) {
Listing (U, V) is the minimum side E = E- = E- (U, V)} / / from E in E
I f ((u, v) is added to T in T in T, add (U, V) to T
}
I f (| T | = = N-1) t is the minimum cost tree
E L S e network is not interconnected, can not find the spanning tree
Figure 13-13 Pseudo code for Kruskao algorithm
(2) Certificate of correctness
Transformation techniques used in the aforementioned load can be proved that the greedy algorithm of Figure 1 3 - 1 3 can always establish a minimum cost tree. It is necessary to prove that the following two points: 1) As long as there is a spanning tree, the K R u s K A L algorithm always produces a spanning tree; 2) The resulting tree has a minimum cost. Let G are arbitrary weighted no-shaped maps (ie G is a unreparable network). From 1 2. 11. 3, it is known and only when a non-mapped is connected. And the edges of the rejected (discard) in the Kruskal algorithm are those that generate loops. The figure formed by the edge of the delete connection chart loop is still a communication map, so if the G is connected at the beginning, the edge of T and E can always form a connectivity diagram. That is, if G is connected, the algorithm will not terminate in E = and | T |
1) Let E are the smallest edges having the minimum cost in T in T. Due to K> 0, this is certainly existed.
2) When e is added to U, a unique loop will be formed. Let F are not on the side of this loop.
Since the T is no loop in T, there is at least one edge in the formed loop is not in T.
As can be seen from the selection method of E and F, V = U {E} - {f} is a spanning tree, and the k-1 edge is not appeared in V in T. It is now shown that V is the same as the same as U. Obviously, V is equivalent to the expense of U. If the E is small, it is impossible to spend a small cost ratio of the tree V. If E is consumed above f, f will be considered before e in the K R u s k A L algorithm. Since F is not in T, the Kruskal algorithm has discarded F when the f can be added to T, so the F and T consume less than or equal to F or equal to F. By selecting E, all these edges are in U, so u must contain a loop, but in fact this is impossible, because u is a spanning tree. The cost of E is higher than that of F will lead to contradictions. The remaining unique may be that E and F have the same cost, which can be seen that V is the same for V.
(3) Selection and complexity analysis of data structure
In order to select a non-decreasing order, you can establish a minimum heap and take out each side from a heap as needed. When there is an e strip edge in the figure, the time initialization of the time initialization and O (L O GE) will be selected for each side. The set T in the side is defined together with the vertices in G, a diagram constructed from up to N connecting sub-maps. With the vertex collection to describe each sub-map, these vertices are not public vertices. In order to determine if the edge (U, V) will generate a loop, only the U, V is set in the same vertices (ie, in the same sub-map). If so, a loop will be formed; if not, there is no loop. Therefore, it is sufficient to use two F i n d for the vertex set. When a side is included in T, 2 subgraphs will be combined into a submap, that is, execute U N I O N operations for two sets. The set F I n D and U N I O N operations can be efficiently performed using a tree (and weighted rules and path compression) of 8. 1 0. 2. The number of f i n d is up to 2E, and the number of updates of UN i o n is N- 1 (if the network is connected, it is just N- 1 time). Plus the initialization time of the tree, this part of this part is only slightly larger than O (N E). The only operation performed on the set T is to add a new side to t. T can be implemented by an array t. Add operation in array
One end is performed, since N- 1 edges can be added to T, thus the total operation of T is O (n).
Summarize the execution time of the various parts described above, the progressive complexity of the algorithm of Fig. 1 3 - 1 3 is O (N EL O GE).
(4) implementation
With the above data structure, Figure 1 - 1 3 can be implemented with a C code. First define the E d g e n o D e class (see programs 1 3 - 6), which is the minimum pile of elements and data types that generate the tree array T.
Data type required by the program 13-6 Kruskal algorithm
Template
Class edgenode {
P U B L i C:
Operator t () const {return weight;}
P R i v a t e:
Tweight; //
INT U, V; / / endpoint
}
In order to use 8. 1 0. 2 sections, the U Nion F Indicate is defined, and its constructor is the initialization function of the program 8 - 1 6, U Nion is the weight of the program 8 - 1 6 Merger functions, F Ind is the path compressed search function of program 8 - 1 7.
In order to write a code-independent code with the network, a new class U N e t Wo R k has also been defined, which contains all functions applied to the unreparable network. This difference between the class and the U N D I R E C TET E-class is that the function in the U N D i R e c TET E-class does not require weighting edges, and u n e t Wo R k requires the weight of the weight. Members in U N e T WO R K need to use the traversal functions such as B E g i n and N e x T VE R t e x defined in the N e T W O R K class. However, the new traversal function not only needs to return the next adjacent vertex, but also returns the weight of the side of this vertex. These traversal functions and other functions that have direction and non-portable networks constitute W N e T W O R K (see programs 1 3-7).
Program 13-7 WNETWORK class
Template
Class Wnetwork: Virtual Public Network
{
PUBLIC:
Virtual Void First (INT I, INT & J, T & C) = 0;
Virtual Void Next (INT I, INT & J, T & C) = 0;
}; Like B e g i n and N e x T Ve R t e x, the function F I R S T and N e x T are added to N e x T in A D J a C e n C Y W D W D I g R A P H. Now A D J a C e n C Y W D I g R A pH and L i N k E d W D I g r A P H can be derived from W N e t Wo R K. Since A D J a C e n c y w g r a p h and L i n k e d w g r a P h need to access member of U N e t w o r k, these two classes must also be booked from U N e t Wo R K. U N e T WO R K:: K R u s K a L code See program 1 3 - 8, it requires EDGES () to define the virtual member of the N e t Work class, and define U N e t Wo R K as the friend of E D g e N o D E). If the tree is not generated, the function returns F A L s E, otherwise returns T R u e. Note When Returning True, returns the minimum tree tree in the array t.
Program 13-8 KR U S K A L Algorithm C Code
Template
Bool Uneetwork
:: Kruskal (Edgenode
t [])
{// Use K R u s k a L algorithm to find a minimum consumption tree
// Return False if it is not connected
// If you connect, you return to the minimum spanning tree in t [0: n - 2].
INT N = VE R T I c e s ();
INT E = Edges ();
/ / Set an array of network edges
InitializePos (); // Drawing Care
Edgenode
* E = new Edgenode
[E 1];
INT K = 0; // e cursor
For (int i = 1; i <= n; i ) {// enable all edges to I
Int J;
T c;
First (i, j, c);
While (j) {// j adjacent to i
IF (i E [ k] .weight = C; E [k] .u = i; E [k] .V = j;} NEXT (I, J, C); } } // put the side to the minimum pile Minheap > H (1); H.INITIALIZE (E, E, E); UnionFind u (n); // Merge / Search Structure / / To extract according to the amount of time K = 0; // This time a cursor While (E && K // The spanning tree is not completed, there are still remaining edges Edgenode X; H.deletemin (x); // minimum spending edge E - -; INT A = u.find (x.u); INT b = u.find (x.v); IF (a! = b) {// select edge T [K ] = x; U. U n i o n (a, b);} } DE A C T I v A T E P O S (); H. d e a c t i v a t e (); Return (k == n - 1); } 2. PRIM algorithm Similar to the KR U S K A L algorithm, the P R I M algorithm creates a minimum spanning tree by selecting multiple edges. Choosing the greedy criterion in the next side is: From the remaining edges, choose a minimal side, and its addition should be a tree in all the selected edges. Finally, a tree is formed while selecting the edges in all steps. Instead, all selected edges in the Kruskal algorithm finally form a forest. The P R I m Algorithm begins with a tree T with a single vertex, which can be any of the vertices in the original image. Then add a minimum side (U, V) to tè {(u, v)}, which is still a tree, which repeatedly circulates until T in T. Note that there is a vertex located in T for both edge (u, v), u, v. The pseudo code of the P R I m algorithm is shown in Figure 1-14. In the pseudo code, the input map is also included is not possible, in which case the tree is generated. Figure 1 - 1 5 shows the process of using the P R I m algorithm to Figures 1-12A. Refined the pseudo code of Figure 1 - 1 4 into C procedures and its correctness certificates to leave the exercise (Exercise 3 1). / / Suppose at least one vertex in the network Set T is the collection of the selected side, initializing T = Set T V as a collection of vertices in the tree, set T v = {1} Let E give a collection in the network W H i L E (E <>) & & (| T | <> N-1) { Order (U, V) is the minimum price side, where u t v, v t v I f (without this side) B RE A K E = E- {(u, v)} / / from E to remove this side Add edges (U, V) in t } IF (| T | = = N- 1) t is a minimum tree The ELSE network is not connected, there is no minimum tree Figure 13-14 PRIM Minimum Generating Tree Algorithm If a vertex NE AR (V) is selected according to the vertex V in the TV, the value of NE AR (V) "and CO ST (V, NE AR (V)) is all such NE AR (V). The smallest in the node, the time complexity of the P rim algorithm is O (N2). The next addition to T is the side: its Cost (V, NEAR (V)) minimizes, and V t v. 3. Sollin algorithm S O L1 N algorithm Each step is selected. At each step, the selected edges and N top points in the figure form a forest in which a tree is generated. Select a side for each tree in the forest, and this is just a vertex in the tree and the price is minimal. Add the selected edge to the spanning tree you want to create. Note that two trees in a forest can choose the same side, so you must copy the same side multiple times. When there are multiple edges having the same cost, the two trees can choose different edges connected to them, in which case one must be discarded. At the beginning, the collections of the selected side are empty. If there is only a tree left or there is no remaining side, the algorithm is terminated. Figure 1 - 6 shows the step of using the S O L i n algorithm when the initial state is shown in Figures 1-12A. When the initial selection of the number is 0, the forest in the forest is a single vertex. The edges selected by the vertices 1, 2,., 7 are (1.6), (2, 7), (3, 4), (5, 4), (6, 1), (7) , 2), where different edges are (1, 6), (2, 7), (3, 4) and (5, 4), and the result obtained after adding these sides into the selected side, as shown in Figure 1 3 - 1 6 A. The next step has a tree selection edge (6, 5), and the remaining two trees are selected (2, 3). After adding these two sides, a spanning tree has been formed, constructing good Generating a tree is shown in Figure 1 3 - 6 B. The c program implementation of the S O L L i n algorithm and its correctness proves to be exercised (Exercise 3 2). Reprinted from Shada Studio
