AntInLoop

Kruskal's Algorithm (Minimum Spanning Tree) Code Implementations

Complete Kruskal's Algorithm (Minimum Spanning Tree) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Kruskal's Algorithm (Minimum Spanning Tree) Guide ยท Launch Interactive Visualizer

C++ Implementation

// Kruskal's Algorithm Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank;
    
public:
    UnionFind(int n) : parent(n), rank(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 rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) return false;
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        
        return true;
    }
};

struct Edge {
    int from, to, weight;
    
    Edge(int from, int to, int weight) : from(from), to(to), weight(weight) {}
    
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

class KruskalAlgorithm {
public:
    static std::vector<Edge> kruskalAlgorithm(std::vector<Edge>& edges, int vertices) {
        // Sort edges by weight
        std::sort(edges.begin(), edges.end());
        
        UnionFind unionFind(vertices);
        std::vector<Edge> mst;
        int totalWeight = 0;
        
        for (const Edge& edge : edges) {
            if (unionFind.unite(edge.from, edge.to)) {
                mst.push_back(edge);
                totalWeight += edge.weight;
                
                // Early termination if we have n-1 edges
                if (mst.size() == vertices - 1) {
                    break;
                }
            }
        }
        
        return mst;
    }
    
    // Kruskal's with adjacency matrix
    static std::vector<Edge> kruskalWithMatrix(const std::vector<std::vector<int>>& adjacencyMatrix) {
        int n = adjacencyMatrix.size();
        std::vector<Edge> edges;
        
        // Convert matrix to edge list
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (adjacencyMatrix[i][j] != 0 && adjacencyMatrix[i][j] != std::numeric_limits<int>::max()) {
                    edges.emplace_back(i, j, adjacencyMatrix[i][j]);
                }
            }
        }
        
        return kruskalAlgorithm(edges, n);
    }
    
    // Kruskal's with adjacency list
    static std::vector<Edge> kruskalWithAdjacencyList(const std::unordered_map<int, std::unordered_map<int, int>>& graph) {
        std::vector<Edge> edges;
        std::unordered_set<int> vertices;
        
        // Convert adjacency list to edge list
        for (const auto& [from, neighbors] : graph) {
            vertices.insert(from);
            for (const auto& [to, weight] : neighbors) {
                if (from < to) {
                    edges.emplace_back(from, to, weight);
                }
            }
        }
        
        return kruskalAlgorithm(edges, vertices.size());
    }
    
    // Kruskal's with cycle detection
    static std::pair<std::vector<Edge>, std::vector<Edge>> kruskalWithCycleDetection(std::vector<Edge>& edges, int vertices) {
        std::sort(edges.begin(), edges.end());
        
        UnionFind unionFind(vertices);
        std::vector<Edge> mst;
        std::vector<Edge> cycles;
        
        for (const Edge& edge : edges) {
            if (unionFind.find(edge.from) == unionFind.find(edge.to)) {
                cycles.push_back(edge);
            } else {
                unionFind.unite(edge.from, edge.to);
                mst.push_back(edge);
            }
        }
        
        return {mst, cycles};
    }
    
    // Calculate total weight of MST
    static int calculateTotalWeight(const std::vector<Edge>& mst) {
        int totalWeight = 0;
        for (const Edge& edge : mst) {
            totalWeight += edge.weight;
        }
        return totalWeight;
    }
};

JAVA Implementation

// Kruskal's Algorithm Implementation in Java
import java.util.*;

class UnionFind {
    private int[] parent;
    private int[] 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 rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) return false;
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        
        return true;
    }
}

class Edge {
    int from, to, weight;
    
    public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}

public class KruskalAlgorithm {
    public static Map<String, Object> kruskalAlgorithm(List<Edge> edges, int vertices) {
        // Sort edges by weight
        edges.sort((a, b) -> Integer.compare(a.weight, b.weight));
        
        UnionFind unionFind = new UnionFind(vertices);
        List<Edge> mst = new ArrayList<>();
        int totalWeight = 0;
        
        for (Edge edge : edges) {
            if (unionFind.union(edge.from, edge.to)) {
                mst.add(edge);
                totalWeight += edge.weight;
                
                // Early termination if we have n-1 edges
                if (mst.size() == vertices - 1) {
                    break;
                }
            }
        }
        
        Map<String, Object> result = new HashMap<>();
        result.put("mst", mst);
        result.put("totalWeight", totalWeight);
        result.put("isComplete", mst.size() == vertices - 1);
        return result;
    }
    
    // Kruskal's with adjacency matrix
    public static Map<String, Object> kruskalWithMatrix(int[][] adjacencyMatrix) {
        int n = adjacencyMatrix.length;
        List<Edge> edges = new ArrayList<>();
        
        // Convert matrix to edge list
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (adjacencyMatrix[i][j] != 0 && adjacencyMatrix[i][j] != Integer.MAX_VALUE) {
                    edges.add(new Edge(i, j, adjacencyMatrix[i][j]));
                }
            }
        }
        
        return kruskalAlgorithm(edges, n);
    }
    
    // Kruskal's with adjacency list
    public static Map<String, Object> kruskalWithAdjacencyList(Map<Integer, Map<Integer, Integer>> graph) {
        List<Edge> edges = new ArrayList<>();
        Set<Integer> vertices = new HashSet<>();
        
        // Convert adjacency list to edge list
        for (Map.Entry<Integer, Map<Integer, Integer>> entry : graph.entrySet()) {
            int from = entry.getKey();
            vertices.add(from);
            Map<Integer, Integer> neighbors = entry.getValue();
            
            for (Map.Entry<Integer, Integer> neighborEntry : neighbors.entrySet()) {
                int to = neighborEntry.getKey();
                int weight = neighborEntry.getValue();
                
                if (from < to) {
                    edges.add(new Edge(from, to, weight));
                }
            }
        }
        
        return kruskalAlgorithm(edges, vertices.size());
    }
    
    // Kruskal's with cycle detection
    public static Map<String, Object> kruskalWithCycleDetection(List<Edge> edges, int vertices) {
        edges.sort((a, b) -> Integer.compare(a.weight, b.weight));
        
        UnionFind unionFind = new UnionFind(vertices);
        List<Edge> mst = new ArrayList<>();
        List<Edge> cycles = new ArrayList<>();
        int totalWeight = 0;
        
        for (Edge edge : edges) {
            if (unionFind.find(edge.from) == unionFind.find(edge.to)) {
                cycles.add(edge);
            } else {
                unionFind.union(edge.from, edge.to);
                mst.add(edge);
                totalWeight += edge.weight;
            }
        }
        
        Map<String, Object> result = new HashMap<>();
        result.put("mst", mst);
        result.put("totalWeight", totalWeight);
        result.put("cycles", cycles);
        result.put("isComplete", mst.size() == vertices - 1);
        return result;
    }
}

JAVASCRIPT Implementation

// Kruskal's Algorithm Implementation in JavaScript
class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    
    if (rootX === rootY) return false;
    
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    
    return true;
  }
}

function kruskalAlgorithm(edges, vertices) {
  // Sort edges by weight
  edges.sort((a, b) => a.weight - b.weight);
  
  const unionFind = new UnionFind(vertices.length);
  const mst = [];
  let totalWeight = 0;
  
  for (const edge of edges) {
    const { from, to, weight } = edge;
    
    if (unionFind.union(from, to)) {
      mst.push(edge);
      totalWeight += weight;
      
      // Early termination if we have n-1 edges
      if (mst.length === vertices.length - 1) {
        break;
      }
    }
  }
  
  return {
    mst,
    totalWeight,
    isComplete: mst.length === vertices.length - 1
  };
}

// Kruskal's with adjacency matrix
function kruskalWithMatrix(adjacencyMatrix) {
  const n = adjacencyMatrix.length;
  const edges = [];
  
  // Convert matrix to edge list
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (adjacencyMatrix[i][j] !== 0 && adjacencyMatrix[i][j] !== Infinity) {
        edges.push({
          from: i,
          to: j,
          weight: adjacencyMatrix[i][j]
        });
      }
    }
  }
  
  return kruskalAlgorithm(edges, Array.from({ length: n }, (_, i) => i));
}

// Kruskal's with adjacency list
function kruskalWithAdjacencyList(graph) {
  const edges = [];
  const vertices = new Set();
  
  // Convert adjacency list to edge list
  for (const [from, neighbors] of Object.entries(graph)) {
    vertices.add(parseInt(from));
    for (const [to, weight] of Object.entries(neighbors)) {
      if (parseInt(from) < parseInt(to)) {
        edges.push({
          from: parseInt(from),
          to: parseInt(to),
          weight: weight
        });
      }
    }
  }
  
  return kruskalAlgorithm(edges, Array.from(vertices));
}

// Kruskal's with cycle detection
function kruskalWithCycleDetection(edges, vertices) {
  edges.sort((a, b) => a.weight - b.weight);
  
  const unionFind = new UnionFind(vertices.length);
  const mst = [];
  const cycles = [];
  let totalWeight = 0;
  
  for (const edge of edges) {
    const { from, to, weight } = edge;
    
    if (unionFind.find(from) === unionFind.find(to)) {
      cycles.push(edge);
    } else {
      unionFind.union(from, to);
      mst.push(edge);
      totalWeight += weight;
    }
  }
  
  return {
    mst,
    totalWeight,
    cycles,
    isComplete: mst.length === vertices.length - 1
  };
}

PYTHON Implementation

# Kruskal's Algorithm Implementation in Python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False
        
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        return True

def kruskal_algorithm(edges, vertices):
    # Sort edges by weight
    edges.sort(key=lambda x: x['weight'])
    
    union_find = UnionFind(len(vertices))
    mst = []
    total_weight = 0
    
    for edge in edges:
        from_vertex = edge['from']
        to_vertex = edge['to']
        weight = edge['weight']
        
        if union_find.union(from_vertex, to_vertex):
            mst.append(edge)
            total_weight += weight
            
            # Early termination if we have n-1 edges
            if len(mst) == len(vertices) - 1:
                break
    
    return {
        'mst': mst,
        'total_weight': total_weight,
        'is_complete': len(mst) == len(vertices) - 1
    }

# Kruskal's with adjacency matrix
def kruskal_with_matrix(adjacency_matrix):
    n = len(adjacency_matrix)
    edges = []
    
    # Convert matrix to edge list
    for i in range(n):
        for j in range(i + 1, n):
            if adjacency_matrix[i][j] != 0 and adjacency_matrix[i][j] != float('inf'):
                edges.append({
                    'from': i,
                    'to': j,
                    'weight': adjacency_matrix[i][j]
                })
    
    vertices = list(range(n))
    return kruskal_algorithm(edges, vertices)

# Kruskal's with adjacency list
def kruskal_with_adjacency_list(graph):
    edges = []
    vertices = set()
    
    # Convert adjacency list to edge list
    for from_vertex, neighbors in graph.items():
        vertices.add(int(from_vertex))
        for to_vertex, weight in neighbors.items():
            if int(from_vertex) < int(to_vertex):
                edges.append({
                    'from': int(from_vertex),
                    'to': int(to_vertex),
                    'weight': weight
                })
    
    return kruskal_algorithm(edges, list(vertices))

# Kruskal's with cycle detection
def kruskal_with_cycle_detection(edges, vertices):
    edges.sort(key=lambda x: x['weight'])
    
    union_find = UnionFind(len(vertices))
    mst = []
    cycles = []
    total_weight = 0
    
    for edge in edges:
        from_vertex = edge['from']
        to_vertex = edge['to']
        weight = edge['weight']
        
        if union_find.find(from_vertex) == union_find.find(to_vertex):
            cycles.append(edge)
        else:
            union_find.union(from_vertex, to_vertex)
            mst.append(edge)
            total_weight += weight
    
    return {
        'mst': mst,
        'total_weight': total_weight,
        'cycles': cycles,
        'is_complete': len(mst) == len(vertices) - 1
    }

# Kruskal's for forest (multiple components)
def kruskal_forest(edges, vertices):
    edges.sort(key=lambda x: x['weight'])
    
    union_find = UnionFind(len(vertices))
    mst_edges = []
    total_weight = 0
    
    for edge in edges:
        from_vertex = edge['from']
        to_vertex = edge['to']
        weight = edge['weight']
        
        if union_find.union(from_vertex, to_vertex):
            mst_edges.append(edge)
            total_weight += weight
    
    return {
        'mst_edges': mst_edges,
        'total_weight': total_weight,
        'components': union_find.parent
    }