【代码随想录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(); // 关闭扫描器}
}