The concept of minimum spanning tree

Suppose we need to set up network communication between nine villages, then we must design a route through all the villages, in order to maximize the cost savings, we need to use the concept of minimum spanning tree.

As shown in figure:

Solution a:

The sum of weights = 11 + 26 + 20 + 24 + 21 + 22 + 19 + 18 = 161

Scheme 2:

The sum of weights = 8 + 12 + 10 + 11 + 17 + 19 + 16 + 7 = 100

Solution 3:

The sum of weights = 11 + 10 + 12 + 8 + 16 + 19 + 16 + 7 = 99

After comparison, it can be seen that the cost of different schemes is different, and the cost of scheme 3 is the least.

So we call the minimum cost spanning tree of constructing a connected network the minimum spanning tree.

There are two classical algorithms to find the minimum spanning tree of a connected network, namely Prim algorithm and Kruskal algorithm.

Second, Prim algorithm

Let’s first construct the adjacency matrix of the graph.

2.1. Idea of Prim algorithm

  1. Let’s pick a vertex, starting with V0. In this case, two paths are available: V1 V5, select the minimum path V1, and the current node is V0 V1
  2. Pick the vertex V5 with the least weight from the edges of V0 V1. The current node is V0 V1 V5
  3. Pick the vertex V8 with the lowest weight from V0 V1 V5. The current node is V0 V1 V5 V8
  4. Select the vertex V2 with the lowest weight from V0 V1 V5 V8. The current node is V0 V1 V5 V8 V2
  5. Select the vertex V6 with the lowest weight from V0 V1 V5 V8 V2
  6. Select vertex V7 with the lowest weight from V0, V1, V5, V8, V2, V6. The current node is V0 V1 V5 V8 V2 V6 V7
  7. V0, V1, V5, V8, V2, V6, V7 The current node is V0 V1 V5 V8 V2 V6 V7 V4
  8. Select V0, V1, V5, V8, V2, V6, V7 V4 from V0, V1, V5, V8, V2, V6, V7 V4. The current node is V0 V1 V5 V8 V2 V6 V7 V4 V3

At step 6, we found that V6->V5 had lower weights than V6->V7, but we chose to go to V7. Because selecting V5 creates a closed loop, which is not what we want, we need to use it in our code to keep track of whether vertices have been added to the spanning tree.

2.2 Prim algorithm implementation

  1. Define two arrays; Adjvex is used to store related vertex subscripts; Lowcost holds the weights between vertices
  2. Initialize two arrays to find the minimum spanning tree starting at V0, which is the first vertex of the minimum spanning tree by default
  3. Loop lowcost, find vertex K based on the weights
  4. Update the Lowcost array
  5. Loop through all vertices, find the vertices related to vertex K, and update the Lowcost array and Adjves array

Update lowcost array and Adjves array conditions:

  1. It’s connected to vertex K
  2. The current node J is not added to the minimum spanning tree
  3. The weight between vertex K and the current vertex J is less than the weight between vertex J and other vertices K, then the update

Code:

#define MAXVEX 20
#define INFINITYC 65535

/* Prim generates the minimum spanning tree */
void MiniSpanTree_Prim(MGraph G) {
    
    int sum = 0;// Minimum path sum (weight)
    int min;// Minimum weight
    int k;// Record the current vertex subscript
    
    // Save the associated vertex subscripts
    int adjvex[MAXVEX];
    // The weight of the edge associated with the saved vertex
    int lowcost[MAXVEX];
    
    
    lowcost[0] = 0;// Starting from V0 indicates that V0 has been added to the minimum spanning tree
    adjvex[0] = 0;// Start with V0
    
    //V0 has been added to the minimum spanning tree
    for (int i = 1; i < G.numVertexes; i++) {
        lowcost[i] = G.arc[0][i];
        adjvex[i] = 0;
    }
    
    // Iterate over vertices, 0 represents V0, no processing required
    for (int i = 1; i < G.numVertexes; i++) {
        
        min = INFINITYC;
        k = 0;

        // Find the minimum weight from lowcost
        for (int j = 0; j < G.numVertexes; j++) {
            if(lowcost[j] ! =0&& lowcost[j] < min) { min = lowcost[j]; k = j; }}printf("(V%d, V%d) = %d\n", adjvex[k], k, G.arc[adjvex[k]][k]);
        sum += G.arc[adjvex[k]][k];
        lowcost[k] = 0;
        
        // Start traversing from the vertex currently added to the minimum spanning tree (adjacency matrix horizontal), update the minimum weight to lowcost,
        for (int z = 1; z < G.numVertexes; z++) {
            if(lowcost[z] ! =0 && G.arc[k][z] < lowcost[z]) {
                lowcost[z] = G.arc[k][z];// Update the minimum weight
                adjvex[z] = k;// Record the minimum weight vertex}}}printf("sum = %d\n", sum);
}
Copy the code

3. Kruskal algorithm

Prim algorithm takes a vertex as a starting point and gradually finds the edge with the least weight on the vertex to form a minimum spanning tree. Kruskal’s algorithm is to build directly with the edge as the target, because the weight is on the edge, directly look for the minimum weight to build, but when building, we need to consider the closed-loop problem.

3.1 Ideas of Kruskal algorithm

  1. Converts the adjacency matrix to an array of edge lists.
  2. The array of side tables is sorted from smallest to largest by weight
  3. Iterate over all edges, using the parent array to find edge connection information, avoiding closed loop problems
  4. If there are no closed-loop problems, add to the minimum spanning tree and modify the parent array

This array of edge tables represents placing weights in order, with begin and end being two vertex subscripts. This records the vertex information and weight information of all edges.

3.2 code implementation

Define an edge table array structure:

Typedef struct {int begin; int end; int weight; } Edge;Copy the code

Concrete implementation:

/* Switch weights and heads and tails */ void Swapn(Edge *edges,int I,int j) {int tempValue; // Switch edges[I].begin and edges[j].begin = edges[I].begin; edges[i].begin = edges[j].begin; edges[j].begin = tempValue; // Switch edges[I].end and edges[j]. End = tempValue = edges[I].end; edges[i].end = edges[j].end; edges[j].end = tempValue; // Switch edges[I]. Weight and edges[j]. edges[i].weight = edges[j].weight; edges[j].weight = tempValue; } /* Sort the weights */ void sort(Edge Edge [],MGraph *G) {for (int i = 0; i < G->numEdges; i++) {
        for (int j = i + 1; j < G->numEdges; j++) {
            if(edges[i].weight > edges[j].weight) { Swapn(edges, i, j); }}}} // Find(int *parent, int f) {while ( parent[f] > 0) {
        f = parent[f];
    }
    returnf; } /* Create a minimum spanning tree */ void MiniSpanTree_Kruskal(MGraph G) {int sum = 0; /* Record the connection between vertices. It is used to prevent the closed-loop of minimum spanning tree. */ int parent[MAXVEX]; Edge edges[MAXVEX]; int k = 0; // Walk through the weight of each edge and related verticesfor (int i = 0; i < G.numVertexes; i++) {
        for (int j = i + 1; j < G.numVertexes; j++) {
            if (G.arc[i][j] < INFINITYC) {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.arc[i][j];
                //printf("(V%d V%d)%d\n", edges[k].begin, edges[k].end, edges[k].weight); k++; }}} // Bubble sort(edges, &g); // Initialize parentfor(int i = 0; i < MAXVEX; i++) { parent[i] = 0; } // Minimum spanning treefor (int i = 0; i < G.numEdges; i++) {
        int n = Find(parent, edges[i].begin);
        int m = Find(parent, edges[i].end);
        if (n != m) {
            parent[n] = m;
            sum += edges[i].weight;
        }
    }
    printf("sum = %d\n", sum);
}
Copy the code

The meaning of parent here is to handle the closed loop, in the minimum spanning tree above:

  1. Begin = 4, parent[4] = 0; end = 7, parent[7] = 0; m = 7, parent = {0, 0, 0, 0, 0, 0, 0, 0, 0; 0, 0, 0};
  2. When I = 1, a begin = 2, the parent [2] = 0 n = 2. End = 8, the parent [8] = 0 m = 8, the parent = {0, 0, 8, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  3. Begin = 0, parent[0] = 0; end = 1, parent[1] = 0; m = 1, parent = {1, 0, 8, 0, 7, 0, 0, 0, 0, 0, 0; 0, 0, 0};
  4. Begin = 0, parent[0] = 1 -> parent[1] = 0, n = 1. End = 5,parent[5] = 0, m = 5,parent = {1, 5, 8, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  5. Begin = 1, parent[1] = 5 -> parent[5] = 0, end = 8,parent[8] = 0 0, 0, 0, 0, 0, 0, 0, 0, 0};
  6. Begin = 3, parent[3] = 0, n = 3. End = 7,parent[7] = 0, m = 7,parent = {1, 5, 8, 7, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0};
  7. Begin = 1, parent[1] = 5 -> parent[5] = 8 -> parent[8] = 0, End = 6,parent = {1, 5, 8, 7, 7, 8, 0, 0, 6, 0, 0, 0, 0, 0};
  8. Begin = 5, parent[5] = 8 -> parent[8] = 6 -> parent[6] = 0, end = 6,parent[6] = 0, In this case, m == n will be closed loop, so do not modify the parent
  9. Begin = 1, parent[1] = 5 -> parent[5] = 8 -> parent[8] = 6 -> parent[6] = 0, End = 2,parent[2] = 8 -> parent[8] = 6 -> parent[6] = 0
  10. When I = 9, begin = 6, the parent [6] = 0, namely, n = 6. End = 7, the parent [7] = 0 m = 7, the parent = {1, 5, 8, 7, 7, 8, 7, 0, 6, 0, 0, 0, 0, 0, 0};
  11. Begin = 7, parent[7] = 0, end = 4,parent[4] = 7 -> parent[7] = 0 So do not modify parent
  12. Begin = 3, parent[3] = 7 -> parent[7] = 0, End = 8,parent[8] = 6 -> parent[6] = 7 -> parent[7] = 0
  13. Begin = 2, parent[2] = 8 -> parent[8] = 6 -> parent[6] = 7 -> parent[7] = 0, End = 3,parent[3] = 7 -> parent[7] = 0
  14. Begin = 3, parent[3] = 7 -> parent[7] = 0, end = 6,parent[6] = 7 -> parent[7] = 0, In this case, m == n will be closed loop, so do not modify the parent
  15. Begin = 4, parent[4] = 7 -> parent[7] = 0, End = 5,parent[5] = 8 -> parent[8] = 6 -> parent[6] = 7 -> parent[7] = 0