最小生成树 Java实现

克鲁斯卡尔算法

import java.util.Arrays;
import java.util.Scanner;

class Edge {
    private int left, right, weight;
    Edge(int left, int right, int weight) {
        this.left = left;
        this.right = right;
        this.weight = weight;
    }

    public int getLeft() {
        return left;
    }

    public int getRight() {
        return right;
    }

    public int getWeight() {
        return weight;
    }

    @Override
    public String toString() {
        return "Edge{" +
                "left=" + left +
                ", right=" + right +
                ", weight=" + weight +
                '}';
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int node = scanner.nextInt();
        int edge = scanner.nextInt();
        Edge[] edges = new Edge[edge];
        for (int i = 0; i < edge; i++) {
            int left = scanner.nextInt();
            int right = scanner.nextInt();
            int weight = scanner.nextInt();
            edges[i] = new Edge(left, right, weight);
        }
        //将边按权值从小到大排序
        Arrays.sort(edges, (a, b) -> a.getWeight() - b.getWeight());
        //并查集，初始化每个节点为独立的集合，每个集合代表一个连通分量
        int[] parent = new int[node];
        for (int i = 0; i < node; i++)
            parent[i] = i;
        //连通图的生成树包含node-1条边
        Edge[] ret = new Edge[node - 1];
        int index = 0;
        for (int i = 0; i < edge; i++) {
            int p1 = find(parent, edges[i].getLeft());
            int p2 = find(parent, edges[i].getRight());
            if (p1 == p2) {
                continue;
            } else {
                //合并连通分量
                parent[p1] = p2;
                ret[index] = edges[i];
                index++;
                if (index == node - 1) {
                    break;
                }
            }
        }
        for (int i = 0; i < index; i++) {
            System.out.println(ret[i]);
        }
    }

    private static int find(int[] parent, int n) {
        if (parent[n] == n) {
            return n;
        }
        else {
            return find(parent, parent[n]);
        }
    }
}

测试输入：

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11

输出

Edge{left=0, right=3, weight=5}
Edge{left=2, right=4, weight=5}
Edge{left=3, right=5, weight=6}
Edge{left=0, right=1, weight=7}
Edge{left=1, right=4, weight=7}
Edge{left=4, right=6, weight=9}

Prim算法

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int node = scanner.nextInt();
        int edge = scanner.nextInt();
        int[][] edges = new int[node][node];
        for (int i = 0; i < node; i++)
            Arrays.fill(edges[i], Integer.MAX_VALUE);
        int ret = 0;
        for (int i = 0; i < edge; i++) {
            int left = scanner.nextInt();
            int right = scanner.nextInt();
            int weight = scanner.nextInt();
            edges[left][right] = weight;
            edges[right][left] = weight;
        }
        boolean[] visited = new boolean[node];
        int[] link = new int[node];
        int[] dist = new int[node];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        for (int i = 0; i < node; i++) {
            int x = -1;
            int d = Integer.MAX_VALUE;
            for (int j = 0; j < node; j++) {
                if (!visited[j]) {
                    if (dist[j] < d) {
                        x = j;
                        d = dist[j];
                    }
                }
            }
            visited[x] = true;
            if (x != link[x])
                System.out.println("left=" + x + ", right=" + link[x] + ", weight=" + d);
            ret += d;
            for (int j = 0; j < node; j++) {
                if (!visited[j]) {
                    if (dist[j] > edges[x][j]) {
                        dist[j] = edges[x][j];
                        link[j] = x;
                    }
                }
            }
        }
        System.out.println(ret);
    }
}

测试输入：

7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
4 6 9
5 6 11

输出

left=3, right=0, weight=5
left=5, right=3, weight=6
left=1, right=0, weight=7
left=4, right=1, weight=7
left=2, right=4, weight=5
left=6, right=4, weight=9
39