This is the sixth day of my participation in Gwen Challenge

What is a minimum spanning tree

A minimum spanning tree is a minimally connected subgraph of a graph that contains all vertices of the original graph and the sum of weights of all edges is as small as possible.

Prim algorithm is one of the minimum spanning tree algorithms of graphs. Prim algorithm is a greedy algorithm to solve the MST problem of weighted undirected connected graphs. It can find a subset of edges such that the tree contains all the vertices in the graph, and the sum of edge weights is minimum.

Prim algorithm is based on the vertex of the graph. From the first initial vertex, it looks for the edge with the lowest weight reaching other vertices, and adds the vertex to the set of “reached vertices”, which is the minimum spanning tree of the graph.

In general, one-dimensional array is more convenient to express the minimum spanning tree. The element corresponding to the array subscript represents the parent node of the vertex in the minimum spanning tree.

Suppose we have a weighted graph like this:

The set formed by the edge with the lowest ownership value is as follows:

Remove the extra edges and you get the minimum spanning tree of the graph instance:

Prim algorithm detailed steps

The following detailed steps of the algorithm are taken from the article comics: What is a Minimum spanning Tree? , to their own understanding of the description

Take the first vertex of the graph as the initial vertex and add it to the set of reached vertices.

The first vertex is always the root of the MST(minimum spanning tree), but since the root has no parent, the element value of the root is -1.

At this point, starting from the set of “reached vertices”, it is found that the weight from 0 to 2 is the lowest. Add vertex 2 to the set of “reached vertices”, because its parent node is the root node, so its element value is 0.

Continue from the set of “reached vertices”, find that 2 to 4 have the lowest weights, add vertex 4 to the set of “reached vertices”, since its parent node is 2, so its element value is 2.

Continue from the set of “reached vertices”, find that 0 to 1 has the lowest weight, add vertex 1 to the set of “reached vertices”, because its parent node is 0, so its element value is 0.

Continue from the set of “reached vertices”, find that 1 to 3 have the lowest weights, add vertex 3 to the set of “reached vertices”, since its parent node is 1, so its element value is 1.

At this point, the set of “reached vertices” is the minimum spanning tree of the weighted graph.

Prim algorithm code implementation

If you look closely, you can see that Prim is very similar to Dijkstra, with only a small number of code differences.

// INF constant holds the infinity of type Number
const INF = Number.MAX_SAFE_INTEGER;
/** * Finds the inner function * from the set of unprocessed vertices that picks out the vertex with the least weight@param {*} Graph needs to compute graph instances of the minimum spanning tree *@param {*} The vertex weights table of the key graph instance *@param {*} The visit Record table of visited Graph instances *@returns {*} Returns the vertex with the lowest weight of all unprocessed vertices in the graph instance * */
const minKey = (graph, key, visited) = > {
  // Initialize min value
  let min = INF; // Initialize the current minimum weight (default is infinity)
  let minIndex = 0; // Store the subscript of the current vertex with the lowest weight
  for (let v = 0; v < graph.length; v++) { // Iterate over the list of vertices in the graph instance
    if (visited[v] === false && key[v] < min) { // If the vertex is not visited and the weight of the vertex is less than the current minimum weight (min)
      min = key[v]; // Update the current minimum weight
      minIndex = v; // Update the subscript of the current least weighted vertex}}// Find the vertex with the lowest weight of all unprocessed vertices in the graph instance and return it
  return minIndex; // Returns the vertex with the lowest weight of all unprocessed vertices in the graph instance
};
/** * Minimum spanning tree algorithm -Prim algorithm *@param {*} Graph needs to compute graph instances of the minimum spanning tree *@returns {*} Minimum spanning tree of graph instance */
export const prim = graph= > {
  const parent = []; // Create a minimum spanning tree array (the minimum spanning tree is represented by a one-dimensional array whose subscripts represent the parent nodes of the vertex in the minimum spanning tree)
  const key = []; // Create an array of vertex weights
  const visited = []; // Create a list of vertices that have been touched
  const { length } = graph; // The number of vertices in the graph instance
  // Initialize the vertex weights array to INF.
  // Initialize the access record table, each vertex access record is not accessed (false)
  for (let i = 0; i < length; i++) {
    key[i] = INF;
    visited[i] = false;
  }
  key[0] = 0; // Select the first key as the first vertex
  parent[0] = -1; // The first vertex is always the root of the MST(minimum spanning tree), but since the root has no parent, the element value of the root is -1, so parent[0]= -1
  // The main loop iterates through all the vertices of the graph instance to find the vertex with the lowest weight in the set of unprocessed vertices
  for (let i = 0; i < length - 1; i++) {
    const u = minKey(graph, key, visited); // Select the vertex with the lowest key value from the unprocessed vertex set, pass graph, key and visited
    visited[u] = true; // Add the current vertex to the touched vertex
    for (let v = 0; v < length; v++) { // Iterate over the vertex (i.e. iterate over the adjacency matrix of the current vertex)
      if(graph[u][v] && ! visited[v] && graph[u][v] < key[v]) {// If you get a smaller weight (the vertex weight exists and is not touched, and the weight of the current collar matrix point is less than the weight of the current record)
        parent[v] = u; // Save to MST path (parent)
        key[v] = graph[u][v]; // Update its weights}}}return parent; // After all vertices are processed, the result containing the minimum spanning tree (MST) is returned
};

Copy the code

The code examples

If the Prim algorithm is executed on the following graph:

let graph = [
 [0.2.4.0.0.0],
 [2.0.2.4.2.0],
 [4.2.0.0.3.0],
 [0.4.0.0.3.2],
 [0.2.3.3.0.2],
 [0.0.0.2.2.0]].Copy the code

You get the following output

/** Edge Weight 0 - 1 2 1 - 2 2 5 - 3 2 1 - 4 2 4 - 5 2 **/
Copy the code