Session 7

		# Prim's Algorithm for Minimum Cost Spanning Tree
 
import heapq
 
 
class PrimsAlgorithm:
    def __init__(self):
        # Adjacency list: vertex -> [(neighbor, weight), ...]
        self.graph = {}
 
    def add_edge(self, u, v, w):
        """Add undirected edge between u and v with weight w"""
        self.graph.setdefault(u, []).append((v, w))
        self.graph.setdefault(v, []).append((u, w))
 
    def prim(self, start_vertex):
        """
        Execute Prim's algorithm from start_vertex.
        Returns: mst_edges, total_cost, step_by_step_log
        """
        mst_edges = []
        total_cost = 0
        visited = set()
        # Min-heap stores: (weight, from_vertex, to_vertex)
        heap = [(0, None, start_vertex)]
        steps = []
 
        print(f"\n{'=' * 70}")
        print(f"PRIM'S ALGORITHM - Starting Vertex: {start_vertex}")
        print(f"{'=' * 70}")
        print(
            f"{'Step':<4} | {'Added':<5} | {'Edge':<8} | {'Weight':<6} | {'Cumulative Cost':<15} | {'MST Edges'}"
        )
        print(f"{'-' * 70}")
 
        while heap and len(visited) < len(self.graph):
            weight, frm, to = heapq.heappop(heap)
 
            # Skip if already included in MST
            if to in visited:
                continue
 
            visited.add(to)
            if frm is not None:
                mst_edges.append((frm, to, weight))
                total_cost += weight
 
                # Log this step
                step_info = {
                    "step": len(steps) + 1,
                    "added": to,
                    "edge": f"{frm}-{to}",
                    "weight": weight,
                    "cost": total_cost,
                    "edges": list(mst_edges),
                }
                steps.append(step_info)
 
                # Print formatted row
                edge_str = ", ".join([f"{u}-{v}" for u, v, _ in mst_edges])
                print(
                    f"{step_info['step']:<4} | {to:<5} | {step_info['edge']:<8} | {weight:<6} | {total_cost:<15} | {edge_str}"
                )
 
            # Explore neighbors
            for neighbor, w in self.graph.get(to, []):
                if neighbor not in visited:
                    heapq.heappush(heap, (w, to, neighbor))
 
        print(f"\n{'=' * 70}")
        print(f"TOTAL MINIMUM COST: {total_cost}")
        print(f"{'=' * 70}")
        return mst_edges, total_cost, steps
 
 
def main():
    prims = PrimsAlgorithm()
 
    # Build the exact graph from the problem image
    edges = [
        ("V1", "V2", 35),
        ("V1", "V4", 20),
        ("V2", "V4", 10),
        ("V2", "V5", 50),
        ("V3", "V4", 22),
        ("V3", "V7", 8),
        ("V4", "V5", 12),
        ("V4", "V8", 5),
        ("V5", "V6", 30),
        ("V5", "V9", 30),
        ("V6", "V10", 9),
        ("V7", "V8", 60),
        ("V8", "V9", 8),
        ("V9", "V10", 16),
    ]
 
    for u, v, w in edges:
        prims.add_edge(u, v, w)
 
    # Run Prim's starting from V1
    prims.prim("V1")
 
 
if __name__ == "__main__":
    main()
	

		/*
 * Prim's Algorithm for Minimum Cost Spanning Tree
*/
 
#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
 
#define V 10  // Number of vertices
#define INF INT_MAX
 
// Map index 0-9 to V1-V10
const char* vertexNames[] = {"V1","V2","V3","V4","V5","V6","V7","V8","V9","V10"};
 
// Find vertex with minimum key value not yet in MST
int minKey(int key[], bool mstSet[]) {
    int min = INF, min_index = -1;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}
 
// Print MST construction steps
void printMST(int parent[], int graph[V][V]) {
    int totalCost = 0;
    printf("\n%-4s | %-5s | %-8s | %-6s | %-15s | %s\n",
           "Step", "Added", "Edge", "Weight", "Cumulative Cost", "MST Edges");
    printf("----------------------------------------------------------------------\n");
 
    for (int i = 1; i < V; i++) {
        int weight = graph[parent[i]][i];
        totalCost += weight;
 
        printf("%-4d | %-5s | %-8s | %-6d | %-15d | ",
               i, vertexNames[i],
               (parent[i] != -1) ? "" : "Root",
               weight, totalCost);
 
        // Print edges built so far
        for (int j = 1; j <= i; j++) {
            if (parent[j] != -1) {
                printf("%s-%s ", vertexNames[parent[j]], vertexNames[j]);
            }
        }
        printf("\n");
    }
    printf("\nTOTAL MINIMUM COST: %d\n", totalCost);
}
 
// Prim's algorithm implementation
void primMST(int graph[V][V]) {
    int parent[V];    // Stores MST structure
    int key[V];       // Key values to pick minimum weight edge
    bool mstSet[V];   // True if vertex is included in MST
 
    // Initialize all keys as INFINITE, mstSet as false
    for (int i = 0; i < V; i++) {
        key[i] = INF;
        mstSet[i] = false;
        parent[i] = -1;
    }
 
    // Start from vertex 0 (V1)
    key[0] = 0;
 
    printf("\n======================================================================\n");
    printf("PRIM'S ALGORITHM - Starting Vertex: V1\n");
    printf("======================================================================\n");
 
    // MST will have V vertices
    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;
 
        // Update key values of adjacent vertices
        for (int v = 0; v < V; v++) {
            // graph[u][v] != 0 means edge exists
            // mstSet[v] == false means v not in MST
            // graph[u][v] < key[v] means new shorter path found
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
    printMST(parent, graph);
}
 
int main() {
    // Adjacency matrix representation of the graph
    // 0 represents no direct edge
    int graph[V][V] = {
        {0, 35, 0, 20, 0, 0, 0, 0, 0, 0},  // V1
        {35, 0, 0, 10, 50, 0, 0, 0, 0, 0}, // V2
        {0, 0, 0, 22, 0, 0, 8, 0, 0, 0},   // V3
        {20, 10, 22, 0, 12, 0, 0, 5, 0, 0},// V4
        {0, 50, 0, 12, 0, 30, 0, 0, 30, 0},// V5
        {0, 0, 0, 0, 30, 0, 0, 0, 0, 9},   // V6
        {0, 0, 8, 0, 0, 0, 0, 60, 0, 0},   // V7
        {0, 0, 0, 5, 0, 0, 60, 0, 8, 0},   // V8
        {0, 0, 0, 0, 30, 0, 0, 8, 0, 16},  // V9
        {0, 0, 0, 0, 0, 9, 0, 0, 16, 0}    // V10
    };
 
    primMST(graph);
    return 0;
}
	

		// Prim's Algorithm for Minimum Cost Spanning Tree
use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashMap, HashSet};
 
// Structure for priority queue items
#[derive(Debug, Eq, PartialEq)]
struct QueueItem {
    weight: i32,
    from: String,
    to: String,
}
 
// Implement min-heap ordering
impl Ord for QueueItem {
    fn cmp(&self, other: &Self) -> Ordering {
        other
            .weight
            .cmp(&self.weight)
            .then_with(|| self.to.cmp(&other.to))
    }
}
 
impl PartialOrd for QueueItem {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
 
struct PrimsAlgorithm {
    adjacency_list: HashMap<String, Vec<(String, i32)>>,
}
 
impl PrimsAlgorithm {
    fn new() -> Self {
        PrimsAlgorithm {
            adjacency_list: HashMap::new(),
        }
    }
 
    fn add_edge(&mut self, u: &str, v: &str, w: i32) {
        self.adjacency_list
            .entry(u.to_string())
            .or_default()
            .push((v.to_string(), w));
        self.adjacency_list
            .entry(v.to_string())
            .or_default()
            .push((u.to_string(), w));
    }
 
    fn run(&self, start: &str) {
        let mut mst_edges = Vec::new();
        let mut total_cost = 0;
        let mut visited = HashSet::new();
        let mut heap = BinaryHeap::new();
 
        heap.push(QueueItem {
            weight: 0,
            from: "Root".to_string(),
            to: start.to_string(),
        });
 
        println!("\n{}", "=".repeat(70));
        println!("PRIM'S ALGORITHM - Starting Vertex: {}", start);
        println!("{}", "=".repeat(70));
        println!(
            "{:<4} | {:<5} | {:<8} | {:<6} | {:<15} | {}",
            "Step", "Added", "Edge", "Weight", "Cumulative Cost", "MST Edges"
        );
        println!("{}", "-".repeat(70));
 
        let mut step = 0;
        while let Some(item) = heap.pop() {
            if visited.contains(&item.to) {
                continue;
            }
 
            visited.insert(item.to.clone());
 
            if item.from != "Root" {
                mst_edges.push((item.from.clone(), item.to.clone(), item.weight));
                total_cost += item.weight;
                step += 1;
 
                let edge_str: Vec<String> = mst_edges
                    .iter()
                    .map(|(u, v, _)| format!("{}-{}", u, v))
                    .collect();
 
                println!(
                    "{:<4} | {:<5} | {:<8} | {:<6} | {:<15} | {}",
                    step,
                    item.to,
                    format!("{}-{}", item.from, item.to),
                    item.weight,
                    total_cost,
                    edge_str.join(" ")
                );
            }
 
            if let Some(neighbors) = self.adjacency_list.get(&item.to) {
                for (neighbor, weight) in neighbors {
                    if !visited.contains(neighbor) {
                        heap.push(QueueItem {
                            weight: *weight,
                            from: item.to.clone(),
                            to: neighbor.clone(),
                        });
                    }
                }
            }
        }
 
        println!("\n{}", "=".repeat(70));
        println!("TOTAL MINIMUM COST: {}", total_cost);
        println!("{}", "=".repeat(70));
    }
}
 
fn main() {
    let mut prim = PrimsAlgorithm::new();
 
    let edges = [
        ("V1", "V2", 35),
        ("V1", "V4", 20),
        ("V2", "V4", 10),
        ("V2", "V5", 50),
        ("V3", "V4", 22),
        ("V3", "V7", 8),
        ("V4", "V5", 12),
        ("V4", "V8", 5),
        ("V5", "V6", 30),
        ("V5", "V9", 30),
        ("V6", "V10", 9),
        ("V7", "V8", 60),
        ("V8", "V9", 8),
        ("V9", "V10", 16),
    ];
 
    for &(u, v, w) in &edges {
        prim.add_edge(u, v, w);
    }
 
    prim.run("V1");
}
	

		class Graph:
    def __init__(self, vertices):
        self.V = vertices  # Total count of nodes
        self.graph = []  # Default storage array for data streams
 
    def add_edge(self, u, v, w):
        """Append an un-directed edge configuration containing weight"""
        self.graph.append([u, v, w])
 
    def find(self, parent, i):
        """Find the root element of element i with path compression technique"""
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])
 
    def union(self, parent, rank, x, y):
        """Perform union of two sets using rank optimization"""
        xroot = self.find(parent, x)
        yroot = self.find(parent, y)
 
        if rank[xroot] < rank[yroot]:
            parent[xroot] = yroot
        elif rank[xroot] > rank[yroot]:
            parent[yroot] = xroot
        else:
            parent[yroot] = xroot
            rank[xroot] += 1
 
    def kruskal_mcst(self):
        result = []  # Stores the final built tree
        i, e = (
            0,
            0,
        )  # i: tracking index for sorted edges, e: tracking count for MCST edges
 
        # Step 1: Sort all edges in non-decreasing order of weight
        self.graph = sorted(self.graph, key=lambda item: item[2])
 
        parent = []
        rank = []
 
        # Create V individual subset components
        for node in range(self.V):
            parent.append(node)
            rank.append(0)
 
        # Process elements until the tree contains exactly V-1 components
        while e < self.V - 1:
            u, v, w = self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent, v)
 
            # If roots are distinct, no cycle is formed. Accept edge.
            if x != y:
                e = e + 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)
 
        # Print out compiled outputs
        minimum_cost = 0
        print("Edges in the constructed MCST (Python Implementation):")
        for u, v, weight in result:
            minimum_cost += weight
            print(f"V{u + 1} -- V{v + 1} == {weight}")
        print(f"Minimum Spanning Tree Cost: {minimum_cost}")
 
 
# Driver execution matching our graph data schema
if __name__ == "__main__":
    g = Graph(10)
    g.add_edge(0, 1, 35)  # V1-V2
    g.add_edge(0, 3, 20)  # V1-V4
    g.add_edge(1, 3, 10)  # V2-V4
    g.add_edge(1, 4, 50)  # V2-V5
    g.add_edge(2, 3, 22)  # V3-V4
    g.add_edge(2, 6, 8)  # V3-V7
    g.add_edge(3, 4, 12)  # V4-V5
    g.add_edge(3, 7, 5)  # V4-V8
    g.add_edge(4, 5, 30)  # V5-V6
    g.add_edge(4, 8, 30)  # V5-V9
    g.add_edge(5, 9, 9)  # V6-V10
    g.add_edge(6, 7, 60)  # V7-V8
    g.add_edge(7, 8, 8)  # V8-V9
    g.add_edge(8, 9, 16)  # V9-V10
 
    g.kruskal_mcst()
	

		#include <stdio.h>
#include <stdlib.h>
 
// Structure to represent a weighted edge in the graph
struct Edge {
    int src, dest, weight;
};
 
// Structure to represent a connected, undirected, and weighted graph
struct Graph {
    int V, E;
    struct Edge* edge;
};
 
// Structure to represent a subset for union-find
struct Subset {
    int parent;
    int rank;
};
 
// Function to create a graph with V vertices and E edges
struct Graph* createGraph(int V, int E) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));
    return graph;
}
 
// A utility function to find set of an element i (uses path compression technique)
int find(struct Subset subsets[], int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}
 
// A function that does union of two sets of u and v (uses union by rank)
void Union(struct Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
 
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
 
// Comparator function used by qsort to sort edges based on their weight
int myComp(const void* a, const void* b) {
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight - b1->weight;
}
 
// The main function to construct MCST using Kruskal's algorithm
void KruskalMCST(struct Graph* graph) {
    int V = graph->V;
    struct Edge result[V];  // Stores the final constructed MCST edges
    int e = 0;  // Index variable used for result[]
    int i = 0;  // Index variable used for sorted edges
 
    // Step 1: Sort all the edges in non-decreasing order of their weight
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
 
    // Allocate memory for creating V subsets
    struct Subset* subsets = (struct Subset*) malloc(V * sizeof(struct Subset));
 
    // Initialize V subsets with single elements
    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
 
    // Number of edges to be taken is equal to V-1
    while (e < V - 1 && i < graph->E) {
        // Step 2: Pick the smallest edge. Check if it forms a cycle
        struct Edge next_edge = graph->edge[i++];
 
        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);
 
        // If including this edge doesn't cause a cycle, include it in result
        if (x != y) {
            result[e++] = next_edge;
            Union(subsets, x, y);
        }
    }
 
    // Print the contents of result[] to display the built MCST
    int minimumCost = 0;
    printf("Edges in the constructed MCST (C Implementation):\n");
    for (i = 0; i < e; ++i) {
        printf("V%d -- V%d == %d\n", result[i].src + 1, result[i].dest + 1, result[i].weight);
        minimumCost += result[i].weight;
    }
    printf("Minimum Spanning Tree Cost: %d\n", minimumCost);
 
    free(subsets);
}
 
int main() {
    int V = 10; // Number of vertices in graph
    int E = 14; // Number of edges in graph
    struct Graph* graph = createGraph(V, E);
 
    // Adding edges matching the problem image data (0-indexed adjustment: V1 -> 0, V2 -> 1...)
    graph->edge[0].src = 0; graph->edge[0].dest = 1; graph->edge[0].weight = 35; // V1-V2
    graph->edge[1].src = 0; graph->edge[1].dest = 3; graph->edge[1].weight = 20; // V1-V4
    graph->edge[2].src = 1; graph->edge[2].dest = 3; graph->edge[2].weight = 10; // V2-V4
    graph->edge[3].src = 1; graph->edge[3].dest = 4; graph->edge[3].weight = 50; // V2-V5
    graph->edge[4].src = 2; graph->edge[4].dest = 3; graph->edge[4].weight = 22; // V3-V4
    graph->edge[5].src = 2; graph->edge[5].dest = 6; graph->edge[5].weight = 8;  // V3-V7
    graph->edge[6].src = 3; graph->edge[6].dest = 4; graph->edge[6].weight = 12; // V4-V5
    graph->edge[7].src = 3; graph->edge[7].dest = 7; graph->edge[7].weight = 5;  // V4-V8
    graph->edge[8].src = 4; graph->edge[8].dest = 5; graph->edge[8].weight = 30; // V5-V6
    graph->edge[9].src = 4; graph->edge[9].dest = 8; graph->edge[9].weight = 30; // V5-V9
    graph->edge[10].src = 5; graph->edge[10].dest = 9; graph->edge[10].weight = 9; // V6-V10
    graph->edge[11].src = 6; graph->edge[11].dest = 7; graph->edge[11].weight = 60;// V7-V8
    graph->edge[12].src = 7; graph->edge[12].dest = 8; graph->edge[12].weight = 8;  // V8-V9
    graph->edge[13].src = 8; graph->edge[13].dest = 9; graph->edge[13].weight = 16; // V9-V10
 
    KruskalMCST(graph);
 
    free(graph->edge);
    free(graph);
    return 0;
}
	

		// Structure representing an edge
#[derive(Debug, Clone, Copy)]
struct Edge {
    src: usize,
    dest: usize,
    weight: i32,
}
 
// Structure representing the Disjoint-Set (Union-Find)
struct DisjointSet {
    parent: Vec<usize>,
    rank: Vec<usize>,
}
 
impl DisjointSet {
    // Initialize standard subsets
    fn new(n: usize) -> Self {
        let parent = (0..n).collect();
        let rank = vec![0; n];
        DisjointSet { parent, rank }
    }
 
    // Find root using path compression technique
    fn find(&mut self, i: usize) -> usize {
        if self.parent[i] != i {
            self.parent[i] = self.find(self.parent[i]);
        }
        self.parent[i]
    }
 
    // Unify two sets by structural rank
    fn union(&mut self, x: usize, y: usize) {
        let xroot = self.find(x);
        let yroot = self.find(y);
 
        if self.rank[xroot] < self.rank[yroot] {
            self.parent[xroot] = yroot;
        } else if self.rank[xroot] > self.rank[yroot] {
            self.parent[yroot] = xroot;
        } else {
            self.parent[yroot] = xroot;
            self.rank[xroot] += 1;
        }
    }
}
 
fn kruskal_mcst(vertices: usize, mut edges: Vec<Edge>) {
    let mut result = Vec::new();
    let mut ds = DisjointSet::new(vertices);
 
    // Step 1: Sort edges in non-decreasing order of weight
    edges.sort_by_key(|edge| edge.weight);
 
    // Step 2: Iterate over sorted edges
    for edge in edges {
        let x = ds.find(edge.src);
        let y = ds.find(edge.dest);
 
        // If roots are distinct, it means adding this edge will not form a cycle
        if x != y {
            result.push(edge);
            ds.union(x, y);
        }
 
        // Optimization: Stop if we've successfully selected V - 1 edges
        if result.len() == vertices - 1 {
            break;
        }
    }
 
    // Display execution details
    let mut minimum_cost = 0;
    println!("Edges in the constructed MCST (Rust Implementation):");
    for edge in result {
        println!("V{} -- V{} == {}", edge.src + 1, edge.dest + 1, edge.weight);
        minimum_cost += edge.weight;
    }
    println!("Minimum Spanning Tree Cost: {}", minimum_cost);
}
 
fn main() {
    let vertices = 10;
    let edges = vec![
        Edge {
            src: 0,
            dest: 1,
            weight: 35,
        },
        Edge {
            src: 0,
            dest: 3,
            weight: 20,
        },
        Edge {
            src: 1,
            dest: 3,
            weight: 10,
        },
        Edge {
            src: 1,
            dest: 4,
            weight: 50,
        },
        Edge {
            src: 2,
            dest: 3,
            weight: 22,
        },
        Edge {
            src: 2,
            dest: 6,
            weight: 8,
        },
        Edge {
            src: 3,
            dest: 4,
            weight: 12,
        },
        Edge {
            src: 3,
            dest: 7,
            weight: 5,
        },
        Edge {
            src: 4,
            dest: 5,
            weight: 30,
        },
        Edge {
            src: 4,
            dest: 8,
            weight: 30,
        },
        Edge {
            src: 5,
            dest: 9,
            weight: 9,
        },
        Edge {
            src: 6,
            dest: 7,
            weight: 60,
        },
        Edge {
            src: 7,
            dest: 8,
            weight: 8,
        },
        Edge {
            src: 8,
            dest: 9,
            weight: 16,
        },
    ];
 
    kruskal_mcst(vertices, edges);
}
	

		Edges in the constructed MCST:
V4 -- V8 == 5
V3 -- V7 == 8
V8 -- V9 == 8
V6 -- V10 == 9
V2 -- V4 == 10
V4 -- V5 == 12
V9 -- V10 == 16
V1 -- V4 == 20
V3 -- V4 == 22
Minimum Spanning Tree Cost: 110