Data structure Interview # 9 – Common operations on graphs # 3 minimum spanning tree

Note: There are related exercises in the interview book, but the idea is relatively unclear, and there are typesetting mistakes. The author has rewritten the relevant books and his own views for your reference.

Common operations on graphs 3. Minimum spanning tree

Minimum spanning tree — a graph that contains all vertices in a weighted graph that do not form a ring and has the lowest sum of weights.

The methods of solving the minimum spanning tree include Prim algorithm and Kruskal algorithm.

For the idea of Prim algorithm: 1) Select a source node from the source node set (only one node is set in the initial source node set); 2) Select the edge with the lowest weight that is connected to the source node set from the remaining nodes. Adds the source node to the source node collection. Then iterate 1), 2).

The graph structure in the following figure contains 7 vertices. The following figure shows the storage structure of the adjacency matrix of the graph.

\

The simulation execution steps are as follows:

Premise: The source node set VertexSet initially has a set of 0 (assuming that it can take any value in 0A6). Initially the initial edge binding EdgeSet is empty.

Step 1: From the set of edges connected to 0, select the edge with the lowest weight, corresponding to the Vertex0 line in the figure above is obviously 2. So the chosen vertex is Vertex3.

Step 2: from the set of edges connected with {0,3}, select the edge with the lowest weight, as shown in the figure below. Obviously, the weight is 5. So the chosen vertex is Vertex2.

The set becomes:

Step 3: from the set of edges connected with {0,3,2}, select the edge with the lowest weight, as shown in the figure below. Obviously, the weight is 4. So the chosen vertex is Vertex6.

The set becomes:

Step 4: from the set of edges connected with {0,3,2,6}, select the edge with the lowest weight, as shown in the figure below. Obviously, the weight is 5. So the chosen vertex is Vertex1.

The set becomes:

Step 5: from the set of edges connected with {0,3,2,6,1}, select the edge with the lowest weight, as shown in the figure below. Obviously, the weight is 2. So the chosen vertex is Vertex4.

The set becomes:

Step 6: from the set of edges connected with {0,3,2,6,1,4}, select the edge with the lowest weight, as shown in the figure below, obviously with weight of 2. So the chosen vertex is Vertex4.

The set becomes:

Finally: the result after traversal is shown in the following 2 figures: that is, all vertices are included, there is no loop, and the weight is minimum.

//inifinity stands for infinity, that is, unreachable.
int g_WeightMatrix[7] [7] = {0.6.5.2,infinity,infinity,infinity,
                                                 6.0,infinity,infinity,2,infinity,4.5,infinity,0,infinity,infinity,7.5.2,infinity,infinity,0.8,infinity,infinity,
                                                 infinity,2,infinity,8.0.10,infinity,
                                                 infinity,infinity,7,infinity,10.0,infinity,
                                                 infinity,4.5,infinity,infinity,infinity,0};
 
template<class vType.int size>
class msTreeType : publicgraphType<vType, size>
{
public:
       voidcreateSpanningGraph(a);voidminimalSpanning(vType sVertex);
       voidprintTreeAndWeight(a);protected:
       vTypesource;             //
       intweights[size][size];  // Weight array
       intedges[size];          Edges [0]=5 indicates that edges exist between 0 and 5.
       intedgeWeights[size];    // Store the weights starting at a vertex.
};
Copy the code

\

1. Create a weight diagram

When we created the weight diagram, we simplified it. I’m just assigning the given array of weights. [With a little modification here, you can manually enter the relationship between vertices and adjacent edges]. Figure storage form: adjacency matrix storage!

template <class vType.int size>
voidmsTreeType<vType,size>::createSpanningGraph()
{
       gSize= size;
       source= 0;                   // Record the initial point is 0.
       for(int i = 0; i < size; i++)
       {
              for(int j =0; j < size; j++)
              {
                     weights[i][j]= g_WeightMatrix[i][j];
                     if(weights[i][j]! =0&& weights[i][j] ! = infinity) { edges[i]= j;// indicates that the line between I and j exists
                     // cout << "edges[ " <
                     }
                     cout<< weights[i][j] << "\t"; } cout<< endl; }}Copy the code

\

2. Minimum spanning tree

1. Ingenious method of recording source node and target node (through array subscript and result value); 2. Store the minimum weight value after each comparison.

template <class vType.int size>
voidmsTreeType<vType,size>::minimalSpanning(vType sVertex)
{
       vType startVertex, endVertex;
       int minWeight;
       source = sVertex;
 
MSTV [5] =true, indicating that node 5 already exists in the set.
//=false, it does not exist.
       bool mstv[size];
 
// Initialize 0 to self, infinity to unreachable.
       for(int j = 0; j < gSize; j++)
       {
              mstv[j]= false;
              edges[j]= source;
              edgeWeights[j]= weights[source][j];
       }
 
       mstv[source]= true;
       edgeWeights[source]= 0;       // Initial Settings
 
       for(int i = 0; i < gSize- 1; i++)
       {
              minWeight= infinity;   
 
// Find the least weighted unidentified vertex from all vertices,v records the vertex,minWeight records the weight value.
              for(int j = 0; j < gSize; j++)
              {
                     if(mstv[j])// point j already exists in MSTV
                     {
                            for(intk=0; k < gSize; k++)
                            {
                                   // Find the edge with the lowest weight from the existing node to the remaining node.
                                   if(! mstv[k]&& weights[j][k] < minWeight) { endVertex= k;/ / purpose
                                          startVertex= j;  / / source
                                          minWeight= weights[j][k]; // Minimum weight}}//endfor k
                     }//endif(mstv[j])
              }//endfor j
 
              mstv[endVertex]= true;
              edges[endVertex]= startVertex;
              edgeWeights[endVertex]= minWeight;
       }//endfor
}
Copy the code

3. Print a tree

template <class vType.int size>
voidmsTreeType<vType,size>::printTreeAndWeight()
{
       inttreeWeight = 0;
       minimalSpanning(source);
      
       cout<< "Source vertex: " << source << endl;
       cout<< "Edges\t\tWeight" << endl;
 
       for(int j = 0; j < gSize; j++)
       {
              if(edgeWeights[j]! =0)
              {
                     treeWeight= treeWeight + edgeWeights[j];
                     cout<< "(" << j << "," <<edges[j]  << ")\t\t"<< edgeWeights[j] << endl;
              }
       }
       cout<< endl;
       cout<< "Tree Weight: " << treeWeight << endl;
}
Copy the code

\