【代码随想录Day55】图论Part07

prim 算法精讲

题目链接/文章讲解：代码随想录

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取顶点数和边数
        int vertexCount = scanner.nextInt();
        int edgeCount = scanner.nextInt();

        // 初始化邻接矩阵，所有值初始化为一个大值，表示无穷大
        int[][] adjacencyMatrix = new int[vertexCount + 1][vertexCount + 1];
        for (int i = 0; i <= vertexCount; i++) {
            Arrays.fill(adjacencyMatrix[i], Integer.MAX_VALUE);
        }

        // 读取边的信息并填充邻接矩阵
        for (int i = 0; i < edgeCount; i++) {
            int startVertex = scanner.nextInt();
            int endVertex = scanner.nextInt();
            int weight = scanner.nextInt();
            adjacencyMatrix[startVertex][endVertex] = weight;
            adjacencyMatrix[endVertex][startVertex] = weight; // 无向图
        }

        // 距离数组，记录每个节点到生成树的最小距离
        int[] minimumDistances = new int[vertexCount + 1];
        Arrays.fill(minimumDistances, Integer.MAX_VALUE);

        // 记录节点是否在生成树中
        boolean[] isInMST = new boolean[vertexCount + 1];

        // Prim算法主循环
        minimumDistances[1] = 0; // 从第一个节点开始
        for (int i = 1; i < vertexCount; i++) {
            int closestVertex = -1;
            int smallestDistance = Integer.MAX_VALUE;

            // 选择距离生成树最近的节点
            for (int j = 1; j <= vertexCount; j++) {
                if (!isInMST[j] && minimumDistances[j] < smallestDistance) {
                    smallestDistance = minimumDistances[j];
                    closestVertex = j;
                }
            }

            // 将最近的节点加入生成树
            isInMST[closestVertex] = true;

            // 更新非生成树节点到生成树的距离
            for (int j = 1; j <= vertexCount; j++) {
                if (!isInMST[j] && adjacencyMatrix[closestVertex][j] < minimumDistances[j]) {
                    minimumDistances[j] = adjacencyMatrix[closestVertex][j];
                }
            }
        }

        // 统计生成树的总权重
        int totalWeight = 0;
        for (int i = 2; i <= vertexCount; i++) {
            totalWeight += minimumDistances[i];
        }

        // 输出结果
        System.out.println(totalWeight);
        scanner.close();
    }
}

kruskal 算法精讲

题目链接/文章讲解：代码随想录

import java.util.*;

class Edge {
    int vertex1, vertex2, weight;

    // Edge构造函数，初始化边的两个顶点和权重
    Edge(int vertex1, int vertex2, int weight) {
        this.vertex1 = vertex1;
        this.vertex2 = vertex2;
        this.weight = weight;
    }
}

public class Main {
    private static final int MAX_NODES = 10001; // 最大节点数
    private static int[] parent = new int[MAX_NODES]; // 存储每个节点的父节点

    // 初始化并查集
    public static void initializeUnionFind() {
        for (int i = 0; i < MAX_NODES; i++) {
            parent[i] = i; // 每个节点的父节点初始化为自身
        }
    }

    // 查找操作，寻找节点的根节点
    public static int find(int node) {
        if (node == parent[node]) {
            return node; // 如果节点是根节点，直接返回
        }
        // 路径压缩，优化查找效率
        return parent[node] = find(parent[node]);
    }

    // 合并两个集合
    public static void union(int node1, int node2) {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 != root2) {
            parent[root2] = root1; // 将一个集合的根节点指向另一个集合的根节点
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int vertexCount = scanner.nextInt(); // 顶点数量
        int edgeCount = scanner.nextInt(); // 边的数量
        List<Edge> edgeList = new ArrayList<>(); // 存储所有边
        int totalWeight = 0; // 最小生成树的权重总和

        // 读取边的信息
        for (int i = 0; i < edgeCount; i++) {
            int vertex1 = scanner.nextInt();
            int vertex2 = scanner.nextInt();
            int weight = scanner.nextInt();
            edgeList.add(new Edge(vertex1, vertex2, weight)); // 添加边到边列表
        }

        // 按照边的权重进行排序
        edgeList.sort(Comparator.comparingInt(edge -> edge.weight));

        // 初始化并查集
        initializeUnionFind();

        // 遍历所有边，执行Kruskal算法
        for (Edge edge : edgeList) {
            int root1 = find(edge.vertex1);
            int root2 = find(edge.vertex2);

            // 如果两个顶点的根节点不同，说明它们不在同一个集合
            if (root1 != root2) {
                totalWeight += edge.weight; // 加入当前边的权重
                union(root1, root2); // 合并两个集合
            }
        }

        // 输出最小生成树的权重总和
        System.out.println(totalWeight);
        scanner.close(); // 关闭扫描器
    }
}