Minimum spanning tree: A spanning tree of a connected graph with n nodes is a minimal connected subgraph of the original graph, contains all n nodes of the original graph, and has the fewest edges that keep the graph connected

Minimum spanning trees can be used to connect locations at minimal cost, such as laying lines, building roads, etc

An example diagram of an undirected connected graph transformed into a minimum spanning tree is as follows:

The minimum spanning tree can be solved by Kruskal algorithm or Prim algorithm

The realization process of these two algorithms, one keeps updating the shortest edge by adding vertices, and the other keeps updating the vertex group by adding edges, are both applied to dynamic programming logic (that is, the sub-branches are not independent and need to rely on the last result to execute and get the final result step by step), and the divide-and-conquer method is mentioned by the way (that is: A large step can be divided into several sub-branches, and as long as the solution of each sub-branch is obtained, the solution of the large step can be solved in a recursive way, such as: quicksort, merge sort).

Prim algorithm

Prim algorithm generates the minimum spanning tree by constantly adding vertices, and updates the shortest edge in each round. Therefore, PRIM algorithm is also called the point method

Case process

Through the process of adding vertices, the algorithm continuously updates the remaining edge to the edge with the minimum distance, and finally generates the minimum spanning tree

The following illustrates the execution process of PRIM algorithm by generating the minimum spanning tree step by step through a case

1. Since every vertex will be included, one vertex is randomly selected to enter set N(new) first, and the rest are in set S(middle), as shown in the figure below. Select vertex A

1. Then select A vertex D with the shortest distance (a-d) from A to all vertices, add D to set N, update the shortest distance between the vertex in New and other vertices, and retain the shortest distance between the vertex in N and other same vertices

3. Then from set N (now A, D), find the vertex F whose vertex is closest to S(B, C, F), and put it into the set N, and update the distance to the remaining vertex, keeping the shortest distance edge

4. Then from the set N (at this point A, D, F), find out the distance S (B, C) in the vertex distance recent B, to the rest of the vertices in the shortest edge of D – S B, into A collection of N, and update the rest of the vertex distance, keep the short side (as the discovery as the result, A coincidence, and the last step screening)

5. Finally, from set N (now A, D, F, B), find the latest vertex B in the distance S (C), and the shortest edge in the remaining vertex S is A-C. At this time, the minimum spanning tree is reached, and the end

Code implementation

Code to achieve the minimum spanning tree results, using the edge array to save

1. Define adjacent array structures and connected graph data

Namely: the set of edge sets that store the results of the minimum spanning tree and the set of adjacency list (store the connection relation between each vertex, namely the current connected graph)

Typedef struct {int fromvex; int tovex; int weight; } LSLinesNode; // Initialize an adjacency matrix, Static int linesList[N][N] = {{0, 6, MAXINT, MAXINT, 11, 14}, {6, 0, 21, MAXINT, MAXINT, 8}, {MAXINT, 21, 0, 15, MAXINT, 18}, {MAXINT, MAXINT, 15, 0, 12, MAXINT}, {11, MAXINT, MAXINT, 12, 0, 16}, {14, 8, 18, MAXINT, 16, 0}, };Copy the code

2. The implementation code is as follows:

Referring to the case flow, the process of adding a point each time will update the other paths in set N to set S, so the implementation logic is as follows:

1. Declare the result set edge array to hold the edge of the minimum spanning tree

2. By default, the edge from the first point to all other vertices is the shortest edge set, which is put into the result edge array (i.e. the first point is added to set N first, and the other vertices are added to set S), and then update the result by updating the edge set later

3. Start from the first edge, traverse all vertices, find the shortest path and update the edge set

4. Find the shortest edge between the ith edge (set N) and other vertices (set S), each time a new vertex is added, the modified vertex is considered to be added to set N, otherwise in set S

5. Add the minimum edge to the corresponding position of the result edge set, and its position is the same as I (change the added new vertex, enter the set N, remove the vertex from S)

6. At the same time, compare all the edges connected to the vertex in S with the shortest edge added to other vertices. If the edge is shorter than the previous edge, all the edges will be replaced and updated, otherwise it will be retained

7. Increase vertex I to enter the next round, and repeat Step 4

In this way, the updated edge set is the minimum spanning tree set.

Void generateMinTreeByPrim() {printf("prim: dot method \n"); Int n = n-1; int n = n-1; int n = n-1; int n = n-1; LSLinesNode nodes[n]; For (int I = 0; i < n - 1; i++) { nodes[i].fromvex = 0; nodes[i].tovex = i + 1; nodes[i].weight = linesList[0][i + 1]; } for (int i = 0; i < n; I ++) {// find the smallest edge to arrange to the front int minIndex = I; int j = i + 1; for (; j < N; j++) { if (nodes[j].weight < nodes[minIndex].weight) { minIndex = j; }} if (minIndex! = i) { LSLinesNode node = nodes[minIndex]; nodes[minIndex] = nodes[i]; nodes[i] = node; } // All endpoints are the remaining vertices, so only need to compare the weight of the current node and the edge of the end point with the remaining corresponding edge weight, the smaller number of edge sets can be replaced to ensure that the inner edges are the smallest for (j = I + 1; j < N; J ++) {// Default edge matrix int weight = linesList[Nodes [I].tovex][nodes[j].tovex]; if (weight < nodes[j].weight) { nodes[j].fromvex = nodes[i].tovex; // Because end nodes are consistent, just replace the weights and initial nodes. Weight = weight; }}}}Copy the code

Kruskal

Kruskal algorithm is to generate the minimum spanning tree by constantly adding edges, and constantly update vertex groups at the same time. Therefore, Kruskal algorithm is also known as the edge addition method

Case process

The logic of this algorithm is to add n-1 edges accumulatively by grouping and adding merging groups continuously, and finally generate minimum spanning tree

The following illustrates the execution process of Kruskal algorithm by generating the minimum spanning tree step by step through a case

1. First add all its edges to the array set of adjacent edges, and then align them in order from smallest to largest. Because Kruskal is also known as edge addition method, it is necessary to add the smallest edge in sequence, and divide each vertex into A group, each group is its corresponding number (A, B, C, D, F are 0, 1, 2, 3, 4 respectively).

Array in article 1 2. From the near side, comparing its fore and aft peak is in the same group, found A in the 0 group (A) one in three groups (D), the two vertices marked as A group, there will be the latter, on the edge of A – D (D) is incorporated into (A) where the former group group (0), and mark has joined 1 side (this case need only join n – 1, That is, 4 edges can generate a minimum spanning tree.

3. Add the second edge from the adjacent array, compare whether its beginning and end vertices are in the same group, find that one is in group 0 (D) and the other is in group 4 (F), and mark the two vertices as a group. Here, merge the group of the latter (F) of d-F edge into the group of the former (D) (group 0), and the mark has added two edges

3. Add the third edge from the adjacent array, compare whether its beginning and end vertices are in the same group, find that one is in group 0 (B) and the other is in group 4 (D), and mark the two vertices as a group. Here, merge the group of the latter (D) of the b-D edge into the group of the former (B) (group 1), and the mark has added three edges

Array to join article 4 4. From the near side, comparing its fore and aft peak is in the same group, found that one in four groups (A) one in four groups (C), the two vertices marked as A group, there will be the latter, on the edge of A – C (C) is incorporated into (A) where the former group (group 1), and mark has joined four sides, results for several groups of four and at this time, The minimum spanning tree is formed. No further action is required

Code implementation

Code to achieve the minimum spanning tree results, using the edge array to save

1. Define adjacent array structures and connected graph data

Namely: the set of edge sets that store the results of the minimum spanning tree and the set of adjacency list (store the connection relation between each vertex, namely the current connected graph)

Typedef struct {int fromvex; int tovex; int weight; } LSLinesNode; // Initialize an adjacency matrix, Static int linesList[N][N] = {{0, 6, MAXINT, MAXINT, 11, 14}, {6, 0, 21, MAXINT, MAXINT, 8}, {MAXINT, 21, 0, 15, MAXINT, 18}, {MAXINT, MAXINT, 15, 0, 12, MAXINT}, {11, MAXINT, MAXINT, 12, 0, 16}, {14, 8, 18, MAXINT, 16, 0}, };  LSLinesNode nodes[count]; // Save the set of all edge arrays, if there is no adjacency matrix from the next logic default has all edge arraysCopy the code

2. The implementation code is as follows:

Refer to the case flow, each time an edge is added, the group of vertices is updated, and the logic is as follows:

1. Sort all edge nodes in ascending order

2. Divide all vertices into a group and declare result, the number of edges of the minimum spanning tree, and the number of edges of the minimum spanning tree that has been obtained

3. Iterate over adjacent nodes of all edges and perform the following operations on all edges

4. If the two vertices are not in the same group, place the back node to the group where the front node belongs. Otherwise, repeat step 4

5. After the group processing is complete, check whether the number of edges required by the minimum spanning tree is obtained. If so, the minimum spanning tree is formed. Otherwise, repeat Step 4 to continue generating

Void getAllLineNodes(LSLinesNode * Nodes, int *count) {*count = getLinesCount(linesList); Int index = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if (linesList[i][j] > 0 && linesList[i][j] < MAXINT) { nodes[index].fromvex = i; nodes[index].tovex = j; nodes[index].weight = linesList[i][j]; index++; }}}} // Void generateMinTreeByKruskal(LSLinesNode *nodes, int count) {printf(" Kruskal: Add edge method \ n "); int count = 0; LSLinesNode nodes[count]; getAllLineNodes(nodes, &count); For (int I = 0; int I = 0; int I = 0; i < count; i++) { for (int j = i; j < count; j++) { if (nodes[i].weight > nodes[j].weight) { LSLinesNode node = nodes[i]; nodes[i] = nodes[j]; nodes[j] = node; } } } int *vertexs[N]; For (int I = 0; int I = 0; i < N; i++) { *(vertexs[i]) = i; } LSLinesNode result[N-1]; Int num = 0; for (int i = 0; i < count; i++) { LSLinesNode node = nodes[i]; Vertexs [node.fromvex]! = vertexs[node.tovex]) { result[num] = node; num++; *(vertexs[node.tovex]) = *(vertexs[node.fromvex]); If (num >= n-1) break; }}}Copy the code