Kruskal

The Kruskal algorithm is a popular algorithm used to find the minimum spanning tree in a graph.

A minimum spanning tree is a subset of the edges of a connected, edge-weighted graph that connects all the vertices together without any cycles and with the minimum possible total edge weight.

Here's how the Kruskal algorithm works:

1. Sort all the edges of the graph in non-decreasing order of their weight.

2. Initialize an empty minimum spanning tree.

3. Iterate through the sorted edges. For each edge:

   • If adding the edge to the minimum spanning tree doesn't form a cycle, add it to the minimum spanning tree.

   • A cycle can be detected using a disjoint-set data structure (union-find).

4. Repeat step 3 until all vertices are included in the minimum spanning tree.

pseudocode:

Kruskal(G):
    // G is the input graph
    n = number of vertices in G
    T = empty set (to store the minimum spanning tree)
    DSU = initializeDisjointSetUnion(n) // Initialize 
    disjoint-set-union data structure
    
    // Sort edges of G in non-decreasing order of weight
    sort edges of G by weight
    
    for each edge (u, v) in sorted order:
        if find(DSU, u) != find(DSU, v): // If u and v are not in the same set
            add (u, v) to T // Add edge to the minimum spanning tree
            union(DSU, u, v) // Merge the sets containing u and v
    
    return T
```

Here, `find` and `union` are operations of the disjoint-set-union data structure:

```
find(DSU, x):
    if DSU[x] != x:
        DSU[x] = find(DSU, DSU[x])
    return DSU[x]

union(DSU, x, y):
    xRoot = find(DSU, x)
    yRoot = find(DSU, y)
    if xRoot != yRoot:
        DSU[yRoot] = xRoot
```

And the initialization of the disjoint-set-union data structure:

```
initializeDisjointSetUnion(n):
    DSU = []
    for i from 1 to n:
        DSU[i] = i
    return DSU
```

This pseudocode assumes that the input graph `G` is represented 
as a list of edges, each edge being a tuple `(u, v, w)` 
where `u` and `v` are the vertices connected by the edge 
and `w` is the weight of the edge.

// Define a class to represent a disjoint set
class DisjointSet {
    constructor(size) {
        this.parent = new Array(size).fill(null).map((_, index) => index);
    }

    find(node) {
        if (this.parent[node] !== node) {
            this.parent[node] = this.find(this.parent[node]);
        }
        return this.parent[node];
    }

    union(nodeA, nodeB) {
        const rootA = this.find(nodeA);
        const rootB = this.find(nodeB);
        if (rootA !== rootB) {
            this.parent[rootB] = rootA;
        }
    }
}

// Define the Kruskal algorithm function
function kruskal(graph) {
    // Sort edges by weight
    graph.sort((a, b) => a[2] - b[2]);

    const disjointSet = new DisjointSet(graph.length);
    const minimumSpanningTree = [];

    for (const edge of graph) {
        const [vertexA, vertexB, weight] = edge;
        if (disjointSet.find(vertexA) !== disjointSet.find(vertexB)) {
            disjointSet.union(vertexA, vertexB);
            minimumSpanningTree.push(edge);
        }
    }

    return minimumSpanningTree;
}

// Example usage
const graph = [
    [0, 1, 4],
    [0, 7, 8],
    [1, 2, 8],
    [1, 7, 11],
    [2, 3, 7],
    [2, 8, 2],
    [2, 5, 4],
    [3, 4, 9],
    [3, 5, 14],
    [4, 5, 10],
    [5, 6, 2],
    [6, 7, 1],
    [6, 8, 6],
    [7, 8, 7]
];

const minimumSpanningTree = kruskal(graph);
console.log(minimumSpanningTree);

In this example, the graph variable represents an adjacency list of the graph, where each edge is represented as an array [vertexA, vertexB, weight].

The kruskal function takes this graph as input and returns the minimum spanning tree in the same format.