Is this the correct code for kruskal?

Question

static class Edge {
    int u, v, w;

    Edge(int u, int v, int w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }
}

static int[] parent, rank;

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

static boolean union(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);

    if (rootA == rootB) return false;

    if (rank[rootA] < rank[rootB]) {
        parent[rootA] = rootB;
    } else if (rank[rootA] > rank[rootB]) {
        parent[rootB] = rootA;
    } else {
        parent[rootB] = rootA;
        rank[rootA]++;
    }

    return true;
}

static int kruskal(ArrayList<Edge> edges, int n) {
    parent = new int[n];
    rank = new int[n];

    for (int i = 0; i < n; i++) parent[i] = i;

    edges.sort((a, b) -> a.w - b.w);

    int mstCost = 0;

    for (Edge e : edges) {
        if (union(e.u, e.v)) {
            mstCost += e.w;
        }
    }

    return mstCost;
}

Answer 1

1. BFS & DFS (Combined)

This version includes the shared graph and visited array management.

Java

import java.util.*;

public class Main {
    static void bfs(int start, ArrayList<Integer>[] adj, boolean[] vis) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        vis[start] = true;

        while (!q.isEmpty()) {
            int u = q.poll();
            System.out.print(u + " ");
            for (int v : adj[u]) {
                if (!vis[v]) {
                    vis[v] = true;
                    q.add(v);
                }
            }
        }
    }

    static void dfs(int u, ArrayList<Integer>[] adj, boolean[] vis) {
        vis[u] = true;
        System.out.print(u + " ");
        for (int v : adj[u]) {
            if (!vis[v]) {
                dfs(v, adj, vis);
            }
        }
    }

    public static void main(String[] args) {
        int n = 6;
        ArrayList<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();

        adj[1].add(2); adj[2].add(1);
        adj[1].add(3); adj[3].add(1);
        adj[2].add(4); adj[4].add(2);
        adj[2].add(5); adj[5].add(2);

        boolean[] vis = new boolean[n];
        System.out.println("BFS Traversal:");
        bfs(1, adj, vis);

        Arrays.fill(vis, false);
        System.out.println("\nDFS Traversal:");
        dfs(1, adj, vis);
    }
}

---

2. BFS Shortest Path (Unweighted)

Finds the number of edges from the source to every other node.

Java

import java.util.*;

public class Main {
    static int[] bfsShortestPath(int start, ArrayList<Integer>[] adj, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        dist[start] = 0;

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.add(v);
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int n = 5;
        ArrayList<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        adj[0].add(1); adj[1].add(0);
        adj[0].add(2); adj[2].add(0);
        adj[1].add(3); adj[3].add(1);
        adj[3].add(4); adj[4].add(3);

        int[] res = bfsShortestPath(0, adj, n);
        for(int i=0; i<n; i++) System.out.println("Node " + i + " distance: " + res[i]);
    }
}

}

Comments

3. Dijkstra's Algorithm (Weighted Shortest Path)
Includes the Pair helper class and priority queue logic.

Java
import java.util.*;

public class Main {
    static class Pair {
        int node, cost;
        Pair(int node, int cost) { this.node = node; this.cost = cost; }
    }

    static int[] dijkstra(int start, ArrayList<Pair>[] adj, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);

        dist[start] = 0;
        pq.add(new Pair(start, 0));

        while (!pq.isEmpty()) {
            Pair cur = pq.poll();
            int u = cur.node;
            if (cur.cost > dist[u]) continue;
            for (Pair edge : adj[u]) {
                if (dist[u] + edge.cost < dist[edge.node]) {
                    dist[edge.node] = dist[u] + edge.cost;
                    pq.add(new Pair(edge.node, dist[edge.node]));
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int n = 4;
        ArrayList<Pair>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        adj[0].add(new Pair(1, 5));
        adj[0].add(new Pair(2, 1));
        adj[2].add(new Pair(1, 2));
        adj[1].add(new Pair(3, 1));

        int[] d = dijkstra(0, adj, n);
        for(int i=0; i<n; i++) System.out.println("Cost to " + i + ": " + d[i]);
    }
}
4. Bellman-Ford (Negative Weights & Cycles)
Includes the negative cycle detection logic.

Java
import java.util.*;

public class Main {
    static class Edge {
        int u, v, w;
        Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
    }

    static int[] bellmanFord(int start, ArrayList<Edge> edges, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, 1000000000);
        dist[start] = 0;

        for (int i = 0; i < n - 1; i++) {
            for (Edge e : edges) {
                if (dist[e.u] != 1000000000 && dist[e.u] + e.w < dist[e.v]) {
                    dist[e.v] = dist[e.u] + e.w;
                }
            }
        }
        return dist;
    }

    static boolean hasNegativeCycle(ArrayList<Edge> edges, int[] dist) {
        for (Edge e : edges) {
            if (dist[e.u] != 1000000000 && dist[e.u] + e.w < dist[e.v]) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int n = 4;
        ArrayList<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 4));
        edges.add(new Edge(1, 2, -6));
        edges.add(new Edge(2, 3, 2));
        edges.add(new Edge(3, 1, 1)); // This creates a negative cycle!

        int[] dist = bellmanFord(0, edges, n);
        if (hasNegativeCycle(edges, dist)) System.out.println("Negative Cycle Detected!");
        else System.out.println("No Negative Cycle.");
    }
}
5. Kruskal's Algorithm (Minimum Spanning Tree)
Includes the Disjoint Set Union (DSU) structure.

Java
import java.util.*;

public class Main {
    static class Edge {
        int u, v, w;
        Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
    }

    static int[] parent, rank;
    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    static boolean union(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (rootA == rootB) return false;
        if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
        else if (rank[rootA] > rank[rootB]) parent[rootB] = rootA;
        else { parent[rootB] = rootA; rank[rootA]++; }
        return true;
    }

    static int kruskal(ArrayList<Edge> edges, int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        edges.sort((a, b) -> a.w - b.w);
        int mstCost = 0;
        for (Edge e : edges) {
            if (union(e.u, e.v)) mstCost += e.w;
        }
        return mstCost;
    }

    public static void main(String[] args) {
        int n = 4;
        ArrayList<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));

        System.out.println("MST Cost: " + kruskal(edges, n));
    }
}