Prim

Prim's algorithm is a greedy algorithm used to find a minimum spanning tree for a weighted undirected graph.

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

Here's a basic overview of how Prim's algorithm works:

1. Choose an arbitrary vertex to start from.

2. Mark this vertex as visited and add all its adjacent edges to a priority queue.

3. While the priority queue is not empty:

   • Remove the edge with the minimum weight from the priority queue.

   • If the adjacent vertex of this edge has not been visited yet:

     • Mark it as visited.

     • Add the edge to the minimum spanning tree.

     • Add all its adjacent edges to the priority queue.

4. Repeat until all vertices are visited.

pseudocode:

Prim(G):
    Initialize an empty set MST to store the minimum spanning tree
    Initialize a priority queue PQ to store vertices with their respective keys
    Initialize a list Key[] to store the key (minimum weight) of each vertex
    Initialize a list Parent[] to store the parent of each vertex in the MST

    for each vertex v in G:
        Key[v] = INFINITY
        Parent[v] = NULL
    
    Choose an arbitrary vertex as the starting point, let's call it start_vertex
    Key[start_vertex] = 0
    Insert start_vertex into PQ with Key[start_vertex] as priority

    while PQ is not empty:
        u = ExtractMin(PQ) // Remove and return the vertex with the minimum key from PQ
        Add u to MST

        for each vertex v adjacent to u:
            if v is in PQ and weight(u, v) < Key[v]:
                Parent[v] = u
                Key[v] = weight(u, v)
                DecreaseKey(PQ, v, Key[v]) // Update the key of v in PQ
    
    return MST

class PriorityQueue {
    constructor() {
        this.queue = [];
    }

    enqueue(element, priority) {
        this.queue.push({ element, priority });
        this.sort();
    }

    dequeue() {
        return this.queue.shift();
    }

    sort() {
        this.queue.sort((a, b) => a.priority - b.priority);
    }

    isEmpty() {
        return !this.queue.length;
    }
}

class Graph {
    constructor() {
        this.adjacencyList = {};
    }

    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) {
            this.adjacencyList[vertex] = [];
        }
    }

    addEdge(vertex1, vertex2, weight) {
        this.adjacencyList[vertex1].push({ node: vertex2, weight });
        this.adjacencyList[vertex2].push({ node: vertex1, weight });
    }

    prim(startingVertex) {
        const priorityQueue = new PriorityQueue();
        const visited = {};
        const minimumSpanningTree = [];

        this.addVertex(startingVertex);
        visited[startingVertex] = true;

        for (const neighbor of this.adjacencyList[startingVertex]) {
            priorityQueue.enqueue(neighbor.node, neighbor.weight);
        }

        while (!priorityQueue.isEmpty()) {
            const { element: vertex, priority: weight } = priorityQueue.dequeue();

            if (!visited[vertex]) {
                visited[vertex] = true;
                minimumSpanningTree.push({ vertex, weight });

                for (const neighbor of this.adjacencyList[vertex]) {
                    if (!visited[neighbor.node]) {
                        priorityQueue.enqueue(neighbor.node, neighbor.weight);
                    }
                }
            }
        }

        return minimumSpanningTree;
    }
}

// Example usage
const graph = new Graph();

graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');

graph.addEdge('A', 'B', 2);
graph.addEdge('A', 'C', 3);
graph.addEdge('B', 'C', 1);
graph.addEdge('B', 'D', 1);
graph.addEdge('C', 'D', 1);
graph.addEdge('C', 'E', 4);
graph.addEdge('D', 'E', 2);

console.log(graph.prim('A'));

In this example, we create a Graph class and a PriorityQueue class to implement Prim's algorithm.

Then we add vertices and edges to the graph, and finally, we call the prim method with a starting vertex ('A' in this case) to find the minimum spanning tree.