This is the 7th day of my participation in Gwen Challenge
What is the Kruskal algorithm
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 a minimum spanning tree used to generate graph structure, and Kruskal algorithm (Chinese name: Kruskal algorithm) is another minimum spanning tree algorithm, using the idea of greedy algorithm.
Kruskal algorithm detailed analysis
The following detailed steps of the algorithm are from the video of the main “WAY_zhong” of STATION B — Animation Demonstration of the Minimum Spanning Tree (Kruskal and Prim) Algorithm
Since the minimum spanning tree is a tree, the following rules must be followed:
1. Because it is a tree structure, no ring can be formed in any structure.
2. All vertices in the graph structure must be connected. Any two vertices can communicate with each other.
3. If the tree has n vertices, it has n-1 edges.
Suppose I have such an undirected band weight diagram
Then take all the edges of the graph instance and put them in a list
And according to the weight of the edge, from small to large
Then take one edge at a time in the list, add it back to the graph instance, and repeat the process…
Each time an edge is added, it determines whether a ring is formed (a ring is formed), and if not, the edge is selected as an edge in the minimum spanning tree.
Instead, if a ring is formed, the edge is discarded and the next edge in the list is judged
The minimum spanning tree is complete until n-1 edges are selected (satisfying the tree-opposite rule), where n is the number of vertices.
For the complete visual algorithm flow, please refer to the video of the original author of station B:
Minimum spanning tree (Kruskal(Kruskal) and Prim(Prim)) algorithm animation demonstration
Code implementation
// INF constant holds the infinity of type Number
const INF = Number.MAX_SAFE_INTEGER;
/** * Checks if this edge already exists in the MST(minimum spanning tree) to avoid loops (look for tail subscripts of connected vertices) *@param {*} I The edge to check (vertex at the beginning of the line) *@param {*} Parent The array of minimum spanning trees corresponding to the graph instance (the array that determines whether edges form loops) *@returns {*} Returns the found edge * */
const find = (i, parent) = > {
while (parent[i]) { // If an array exists in the minimum spanning tree, pass the value to I
i = parent[i]; // eslint-disable-line prefer-destructuring
}
return i; // Return the found edge
};
/** * Check if the MST(minimum spanning tree) edges are the same *@param {*} I the edge I * that needs to be checked@param {*} J the edge that we need to check j star@param {*} An array of the smallest spanning tree that corresponds to the parent graph instance@returns {*} Returns whether edges are equal, true for different, false for same * */
const union = (i, j, parent) = > {
// Determine whether two nodes are in the same tree, i.e. whether they intersect
if(i ! == j) {// If I and j are different edges, this edge does not loop with the existing spanning tree, add them to the minimum spanning tree (MST)
parent[j] = i; // j is the parent node, and I is the edge weight
return true;
}
return false;
};
/** * The inner function that copies the entire graph and initializes the weights *@param {*} Graph graph instance *@returns {*} Returns the copied and initialized graph instance * */
const initializeCost = graph= > {
const cost = [];
const { length } = graph;
for (let i = 0; i < length; i++) {
cost[i] = [];
for (let j = 0; j < length; j++) {
if (graph[i][j] === 0) {
cost[i][j] = INF;
} else{ cost[i][j] = graph[i][j]; }}}return cost;
};
/** * Minimum spanning tree algorithm - Kruskal algorithm *@param {*} Graph needs to compute graph instances of the minimum spanning tree *@returns {*} Minimum spanning tree of graph instance */
export const kruskal = graph= > {
const { length } = graph; // The number of vertices in the graph instance
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)
let ne = 0; // The minimum number of spanning tree edges
let a;
let b;
let u;
let v;
const cost = initializeCost(graph); // First, copy the value of the adjacency matrix into the COST array to make it easier to modify and keep the original value rows
while (ne < length - 1) { // When the number of MST edges is less than the total number of vertices minus 1 (for a tree with n vertices, its edges are its total number of vertices minus 1)
// Find the edge with the lowest weight
for (let i = 0, min = INF; i < length; i++) { // Iterate over all vertices of the graph, initializing the current minimum weight -min(default is infinite)
for (let j = 0; j < length; j++) { // Iterate over the adjacency matrix of the current vertex
if (cost[i][j] < min) { // If the weight of the edge currently traversed is less than the minimum edge currently recorded (min)
min = cost[i][j]; // Update the minimum weight of the current record
a = u = i; // A and u record the starting vertex of the smallest edge currently stored
b = v = j; // b and v record the arrival of the smallest edge currently stored
}
}
}
u = find(u, parent); // Check whether this edge already exists in the MST(minimum spanning tree) by subscript (i.e., parent node) to avoid loops
v = find(v, parent); // Check whether this edge already exists in the MST(minimum spanning tree) by subscript (i.e., parent node) to avoid loops
if (union(u, v, parent)) { // If u and V are different edges (different parent nodes, no loop), add them to MST(minimum spanning tree)
ne++; // The minimum number of spanning tree edges
}
cost[a][b] = cost[b][a] = INF; // Remove the edges from the list to avoid double-counting
}
// Return MST(minimum spanning tree)
return parent;
};
Copy the code