Kruskal's Algorithm

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

struct Edge {
    int u, v, weight;
};

// Check if selected edges form a spanning tree
bool isSpanningTree(vector<Edge>& selected, int V) {
    // BFS/DFS to check connectivity
    vector<vector<int>> adj(V);
    for (auto& e : selected) {
        adj[e.u].push_back(e.v);
        adj[e.v].push_back(e.u);
    }
    vector<bool> visited(V, false);
    vector<int> stack = {0};
    visited[0] = true;
    int count = 1;
    while (!stack.empty()) {
        int node = stack.back();
        stack.pop_back();
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                count++;
                stack.push_back(neighbor);
            }
        }
    }
    return count == V;
}

pair<vector<Edge>, int> bruteForceMST(
    vector<Edge>& edges, int V) {
    int E = edges.size();
    int target = V - 1;
    vector<Edge> bestMST;
    int bestWeight = INT_MAX;

    // Generate all combinations of (V-1) edges
    vector<int> indices(target);
    for (int i = 0; i < target; i++)
        indices[i] = i;

    while (true) {
        vector<Edge> selected;
        int totalWeight = 0;
        for (int idx : indices) {
            selected.push_back(edges[idx]);
            totalWeight += edges[idx].weight;
        }
        if (isSpanningTree(selected, V)
            && totalWeight < bestWeight) {
            bestWeight = totalWeight;
            bestMST = selected;
        }

        // Next combination
        int i = target - 1;
        while (i >= 0 && indices[i] == E - target + i)
            i--;
        if (i < 0) break;
        indices[i]++;
        for (int j = i + 1; j < target; j++)
            indices[j] = indices[j-1] + 1;
    }

    return {bestMST, bestWeight};
}

from itertools import combinations
from collections import deque

def is_spanning_tree(selected_edges, V):
    """Check if selected edges connect all V vertices."""
    adj = [[] for _ in range(V)]
    for u, v, w in selected_edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * V
    visited[0] = True
    queue = deque([0])
    count = 1
    while queue:
        node = queue.popleft()
        for neighbor in adj[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                count += 1
                queue.append(neighbor)
    return count == V

def brute_force_mst(edges, V):
    best_weight = float('inf')
    best_mst = []

    # Try all combinations of V-1 edges
    for combo in combinations(edges, V - 1):
        if is_spanning_tree(combo, V):
            total = sum(w for _, _, w in combo)
            if total < best_weight:
                best_weight = total
                best_mst = list(combo)

    return best_mst, best_weight

import java.util.*;

class BruteForceMST {
    static boolean isSpanningTree(
        int[][] selected, int V) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());
        for (int[] e : selected) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        boolean[] visited = new boolean[V];
        visited[0] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        int count = 1;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int nb : adj.get(node)) {
                if (!visited[nb]) {
                    visited[nb] = true;
                    count++;
                    queue.add(nb);
                }
            }
        }
        return count == V;
    }

    static int bruteForceMST(
        int[][] edges, int V) {
        int E = edges.length;
        int target = V - 1;
        int bestWeight = Integer.MAX_VALUE;

        // Generate all combinations using
        // recursive backtracking
        int[] indices = new int[target];
        for (int i = 0; i < target; i++)
            indices[i] = i;

        while (true) {
            int[][] selected = new int[target][];
            int total = 0;
            for (int i = 0; i < target; i++) {
                selected[i] = edges[indices[i]];
                total += edges[indices[i]][2];
            }
            if (isSpanningTree(selected, V)
                && total < bestWeight) {
                bestWeight = total;
            }
            int i = target - 1;
            while (i >= 0
                && indices[i] == E - target + i)
                i--;
            if (i < 0) break;
            indices[i]++;
            for (int j = i + 1; j < target; j++)
                indices[j] = indices[j-1] + 1;
        }
        return bestWeight;
    }
}

Kruskal's with DFS Cycle Detection — Watch Kruskal's algorithm process edges from lightest to heaviest, using DFS to check for cycles before adding each edge to the MST.

#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v, weight;
};

bool canReach(int src, int dest, int V,
    vector<vector<pair<int,int>>>& adj) {
    vector<bool> visited(V, false);
    vector<int> stack = {src};
    visited[src] = true;
    while (!stack.empty()) {
        int node = stack.back();
        stack.pop_back();
        if (node == dest) return true;
        for (auto [nb, w] : adj[node]) {
            if (!visited[nb]) {
                visited[nb] = true;
                stack.push_back(nb);
            }
        }
    }
    return false;
}

pair<vector<Edge>, int> kruskalWithDFS(
    vector<Edge>& edges, int V) {
    sort(edges.begin(), edges.end(),
        [](const Edge& a, const Edge& b) {
            return a.weight < b.weight;
        });

    vector<vector<pair<int,int>>> adj(V);
    vector<Edge> mst;
    int totalWeight = 0;

    for (auto& e : edges) {
        if (mst.size() == V - 1) break;

        if (!canReach(e.u, e.v, V, adj)) {
            mst.push_back(e);
            totalWeight += e.weight;
            adj[e.u].push_back({e.v, e.weight});
            adj[e.v].push_back({e.u, e.weight});
        }
    }

    return {mst, totalWeight};
}

from collections import defaultdict

def can_reach(src, dest, adj):
    """DFS to check if dest is reachable from src."""
    visited = set()
    stack = [src]
    visited.add(src)
    while stack:
        node = stack.pop()
        if node == dest:
            return True
        for neighbor, _ in adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    return False

def kruskal_with_dfs(edges, V):
    # Sort edges by weight
    edges.sort(key=lambda e: e[2])

    adj = defaultdict(list)
    mst = []
    total_weight = 0

    for u, v, w in edges:
        if len(mst) == V - 1:
            break

        # DFS cycle detection
        if not can_reach(u, v, adj):
            mst.append((u, v, w))
            total_weight += w
            adj[u].append((v, w))
            adj[v].append((u, w))

    return mst, total_weight

import java.util.*;

class KruskalDFS {
    static boolean canReach(int src, int dest,
        List<List<int[]>> adj, int V) {
        boolean[] visited = new boolean[V];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(src);
        visited[src] = true;
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (node == dest) return true;
            for (int[] nb : adj.get(node)) {
                if (!visited[nb[0]]) {
                    visited[nb[0]] = true;
                    stack.push(nb[0]);
                }
            }
        }
        return false;
    }

    static int kruskalWithDFS(
        int[][] edges, int V) {
        Arrays.sort(edges,
            (a, b) -> a[2] - b[2]);

        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());

        int totalWeight = 0;
        int edgesAdded = 0;

        for (int[] e : edges) {
            if (edgesAdded == V - 1) break;
            if (!canReach(e[0], e[1], adj, V)) {
                totalWeight += e[2];
                edgesAdded++;
                adj.get(e[0]).add(
                    new int[]{e[1], e[2]});
                adj.get(e[1]).add(
                    new int[]{e[0], e[2]});
            }
        }
        return totalWeight;
    }
}

Kruskal's Algorithm with Union-Find — Building the MST — Watch how Kruskal's algorithm processes edges from lightest to heaviest, using Union-Find for near-instant cycle detection to build the minimum spanning tree.

#include <vector>
#include <algorithm>
using namespace std;

class UnionFind {
    vector<int> parent, rank_;
public:
    UnionFind(int n) {
        parent.resize(n);
        rank_.resize(n, 0);
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank_[rx] == rank_[ry]) rank_[rx]++;
        return true;
    }
};

struct Edge {
    int u, v, weight;
};

pair<vector<Edge>, int> kruskal(
    vector<Edge>& edges, int V) {
    // Step 1: Sort edges by weight
    sort(edges.begin(), edges.end(),
        [](const Edge& a, const Edge& b) {
            return a.weight < b.weight;
        });

    // Step 2: Initialize Union-Find
    UnionFind uf(V);
    vector<Edge> mst;
    int totalWeight = 0;

    // Step 3: Process edges greedily
    for (auto& e : edges) {
        if (mst.size() == V - 1) break;

        // If u and v are in different
        // components, add edge
        if (uf.unite(e.u, e.v)) {
            mst.push_back(e);
            totalWeight += e.weight;
        }
    }

    return {mst, totalWeight};
}

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True


def kruskal(edges, V):
    # Step 1: Sort edges by weight
    edges.sort(key=lambda e: e[2])

    # Step 2: Initialize Union-Find
    uf = UnionFind(V)
    mst = []
    total_weight = 0

    # Step 3: Process edges greedily
    for u, v, w in edges:
        if len(mst) == V - 1:
            break

        # If u and v are in different
        # components, add edge
        if uf.union(u, v):
            mst.append((u, v, w))
            total_weight += w

    return mst, total_weight

import java.util.*;

class UnionFind {
    private int[] parent, rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    public int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) {
            int tmp = rx; rx = ry; ry = tmp;
        }
        parent[ry] = rx;
        if (rank[rx] == rank[ry]) rank[rx]++;
        return true;
    }
}

class Kruskal {
    public static int kruskal(
        int[][] edges, int V) {
        // Step 1: Sort edges by weight
        Arrays.sort(edges,
            (a, b) -> a[2] - b[2]);

        // Step 2: Initialize Union-Find
        UnionFind uf = new UnionFind(V);
        int totalWeight = 0;
        int edgesAdded = 0;

        // Step 3: Process edges greedily
        for (int[] e : edges) {
            if (edgesAdded == V - 1) break;

            if (uf.union(e[0], e[1])) {
                totalWeight += e[2];
                edgesAdded++;
            }
        }

        return totalWeight;
    }
}