贵阳市网站建设_网站建设公司_Photoshop_seo优化

一、基础概念

1.1 最小生成树定义

最小生成树（Minimum Spanning Tree, MST）：在带权连通无向图中，找到一个边的子集，使得：

1. 包含所有顶点

2. 没有环

3. 边的总权重最小

1.2 应用场景

• 网络设计：以最小成本连接所有城市

• 电路设计：以最短线路连接所有元件

• 聚类分析：数据点之间的最小连接

• 图像分割：像素点之间的最小分割

二、Kruskal算法

2.1 核心思想

贪心策略：每次选择权重最小且不会形成环的边

2.2 算法步骤

text

复制

下载

1. 将图中所有边按权重从小到大排序 2. 初始化一个空集合用于存放MST的边 3. 初始化并查集，每个顶点自成独立集合 4. 按权重从小到大遍历每条边(u, v)： a. 如果u和v不在同一个集合（即不连通） b. 将边(u, v)加入MST c. 合并u和v所在的集合 5. 当MST包含n-1条边时结束

篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc

需要全套面试笔记及答案
【点击此处即可/免费获取】​​​

2.3 代码实现

java

复制

下载

import java.util.*; public class KruskalMST { static class Edge implements Comparable<Edge> { int src, dest, weight; public Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } @Override public int compareTo(Edge other) { return this.weight - other.weight; } } static class UnionFind { int[] parent; 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[rootY] = rootX; } else if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else { parent[rootY] = rootX; rank[rootX]++; } return true; } } public static List<Edge> kruskalMST(int vertices, List<Edge> edges) { // 1. 按权重排序边 Collections.sort(edges); // 2. 初始化 List<Edge> mst = new ArrayList<>(); UnionFind uf = new UnionFind(vertices); // 3. 处理每条边 for (Edge edge : edges) { if (mst.size() == vertices - 1) { break; // MST已构建完成 } // 4. 检查是否形成环 if (uf.union(edge.src, edge.dest)) { mst.add(edge); } } return mst; } public static void main(String[] args) { int vertices = 4; List<Edge> edges = Arrays.asList( new Edge(0, 1, 10), new Edge(0, 2, 6), new Edge(0, 3, 5), new Edge(1, 3, 15), new Edge(2, 3, 4) ); List<Edge> mst = kruskalMST(vertices, edges); System.out.println("Kruskal MST edges:"); int totalWeight = 0; for (Edge edge : mst) { System.out.println(edge.src + " - " + edge.dest + " : " + edge.weight); totalWeight += edge.weight; } System.out.println("Total weight: " + totalWeight); } }

2.4 时间复杂度分析

text

复制

下载

排序边：O(E log E) 或 O(E log V)（因为E ≤ V²） 并查集操作：每个union/find近似O(α(V))，其中α是反阿克曼函数 总复杂度：O(E log E) 或 O(E log V) 空间复杂度：O(V + E)

2.5 适用场景

• 边数相对较少的稀疏图

• 边权重需要频繁更新

• 分布式计算环境

三、Prim算法

3.1 核心思想

顶点扩展策略：从一个顶点开始，逐步扩展生成树

3.2 算法步骤

text

复制

下载

1. 从任意顶点开始，加入MST集合 2. 初始化优先队列（最小堆），存放从MST到非MST顶点的所有边 3. 当MST包含所有顶点时结束： a. 从优先队列取出权重最小的边(u, v) b. 如果v不在MST中： - 将边(u, v)加入MST - 将v加入MST集合 - 将与v相连且另一端不在MST的边加入优先队列

3.3 代码实现

java

复制

下载

import java.util.*; public class PrimMST { static class Edge { int dest, weight; public Edge(int dest, int weight) { this.dest = dest; this.weight = weight; } } static class Pair implements Comparable<Pair> { int vertex; int weight; int parent; // 记录来源顶点 public Pair(int vertex, int weight, int parent) { this.vertex = vertex; this.weight = weight; this.parent = parent; } @Override public int compareTo(Pair other) { return this.weight - other.weight; } } public static List<int[]> primMST(int vertices, List<List<Edge>> graph) { // 1. 初始化 boolean[] inMST = new boolean[vertices]; PriorityQueue<Pair> minHeap = new PriorityQueue<>(); List<int[]> mstEdges = new ArrayList<>(); // 2. 从顶点0开始 minHeap.offer(new Pair(0, 0, -1)); int edgesAdded = 0; int totalWeight = 0; while (!minHeap.isEmpty() && edgesAdded < vertices) { // 3. 取出最小权重的边 Pair current = minHeap.poll(); int u = current.vertex; // 4. 如果顶点已在MST中，跳过 if (inMST[u]) { continue; } // 5. 加入MST inMST[u] = true; totalWeight += current.weight; if (current.parent != -1) { mstEdges.add(new int[]{current.parent, u, current.weight}); edgesAdded++; } // 6. 将相邻边加入优先队列 for (Edge edge : graph.get(u)) { int v = edge.dest; int weight = edge.weight; if (!inMST[v]) { minHeap.offer(new Pair(v, weight, u)); } } } System.out.println("Prim MST total weight: " + totalWeight); return mstEdges; } // 邻接表表示法 public static List<List<Edge>> createGraph(int vertices, int[][] edges) { List<List<Edge>> graph = new ArrayList<>(); for (int i = 0; i < vertices; i++) { graph.add(new ArrayList<>()); } for (int[] edge : edges) { int u = edge[0], v = edge[1], w = edge[2]; graph.get(u).add(new Edge(v, w)); graph.get(v).add(new Edge(u, w)); // 无向图 } return graph; } public static void main(String[] args) { int vertices = 5; int[][] edges = { {0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8}, {1, 4, 5}, {2, 4, 7}, {3, 4, 9} }; List<List<Edge>> graph = createGraph(vertices, edges); List<int[]> mst = primMST(vertices, graph); System.out.println("Prim MST edges:"); for (int[] edge : mst) { System.out.println(edge[0] + " - " + edge[1] + " : " + edge[2]); } } }

3.4 优化版本：使用优先队列和key数组

java

复制

下载

public class PrimOptimized { public static int primMST(int vertices, int[][] graph) { // key数组：存储到达每个顶点的最小权重 int[] key = new int[vertices]; // parent数组：存储MST中每个顶点的父节点 int[] parent = new int[vertices]; boolean[] inMST = new boolean[vertices]; // 初始化 Arrays.fill(key, Integer.MAX_VALUE); Arrays.fill(parent, -1); key[0] = 0; PriorityQueue<int[]> minHeap = new PriorityQueue<>( (a, b) -> a[1] - b[1] ); minHeap.offer(new int[]{0, key[0]}); while (!minHeap.isEmpty()) { int[] current = minHeap.poll(); int u = current[0]; if (inMST[u]) continue; inMST[u] = true; // 遍历所有相邻顶点 for (int v = 0; v < vertices; v++) { if (graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v]) { key[v] = graph[u][v]; parent[v] = u; minHeap.offer(new int[]{v, key[v]}); } } } // 计算总权重 int totalWeight = 0; for (int i = 1; i < vertices; i++) { totalWeight += graph[i][parent[i]]; } return totalWeight; } }

3.5 时间复杂度分析

text

复制

下载

使用二叉堆：O((V + E) log V) ≈ O(E log V) 使用斐波那契堆：O(E + V log V) 空间复杂度：O(V + E)

3.6 适用场景

• 稠密图（边数接近V²）

• 需要频繁查询MST

• 图结构动态变化

四、算法对比分析

4.1 对比表格

4.2 选择建议

text

复制

下载

if (图是稠密的 && 使用邻接矩阵) { 选择Prim算法 } else if (图是稀疏的 && 边已排序) { 选择Kruskal算法 } else if (需要频繁更新边权重) { 选择Kruskal算法 } else if (需要频繁查询MST) { 选择Prim算法 }

五、实际应用示例

5.1 网络布线问题

java

复制

下载

public class NetworkCabling { // 城市连接问题 public static int minimumCableLength(int n, int[][] connections) { // Kruskal实现 List<Edge> edges = new ArrayList<>(); for (int[] conn : connections) { edges.add(new Edge(conn[0], conn[1], conn[2])); } List<Edge> mst = KruskalMST.kruskalMST(n, edges); return mst.stream().mapToInt(e -> e.weight).sum(); } // 检查网络连通性 public static boolean isNetworkConnected(int n, int[][] connections) { UnionFind uf = new UnionFind(n); for (int[] conn : connections) { uf.union(conn[0], conn[1]); } int root = uf.find(0); for (int i = 1; i < n; i++) { if (uf.find(i) != root) { return false; } } return true; } }

5.2 图像分割应用

java

复制

下载

public class ImageSegmentation { // 像素网格生成最小生成树 public static List<Edge> segmentImage(int width, int height, int[][] pixelWeights) { int vertices = width * height; List<Edge> edges = new ArrayList<>(); // 构建4-connected网格图 for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { int current = i * width + j; // 向右连接 if (j < width - 1) { int right = i * width + (j + 1); int weight = Math.abs(pixelWeights[i][j] - pixelWeights[i][j + 1]); edges.add(new Edge(current, right, weight)); } // 向下连接 if (i < height - 1) { int down = (i + 1) * width + j; int weight = Math.abs(pixelWeights[i][j] - pixelWeights[i + 1][j]); edges.add(new Edge(current, down, weight)); } } } return KruskalMST.kruskalMST(vertices, edges); } }

篇幅限制下面就只能给大家展示小册部分内容了。整理了一份核心面试笔记包括了：Java面试、Spring、JVM、MyBatis、Redis、MySQL、并发编程、微服务、Linux、Springboot、SpringCloud、MQ、Kafc

需要全套面试笔记及答案
【点击此处即可/免费获取】​​​

六、算法变种与优化

6.1 适用于不同场景的变种

java

复制

下载

// 1. 最大生成树（只需修改排序或比较规则） class MaxSpanningTree { public static List<Edge> kruskalMaxST(List<Edge> edges, int vertices) { // 按权重降序排序 Collections.sort(edges, (a, b) -> b.weight - a.weight); // 其余与Kruskal相同 } } // 2. 第K小生成树 class KthMinimumSpanningTree { // 基于MST的边交换策略 } // 3. 度限制生成树 class DegreeConstrainedMST { // 每个顶点有最大连接数限制 }

6.2 性能优化技巧

java

复制

下载

// 1. 边排序优化 // 对于整数权重，可以使用计数排序 O(E + W) public static void countingSortEdges(Edge[] edges, int maxWeight) { // 实现计数排序 } // 2. 内存优化：使用基本类型数组 class PrimMemoryOptimized { // 使用int[][]代替对象，减少内存开销 } // 3. 增量更新：当图动态变化时 class DynamicMST { // 当增加或删除边时，增量更新MST }

七、面试常见问题

7.1 理论问题

1. 证明Kruskal和Prim算法的正确性

2. 两个算法的时间复杂度推导过程

3. 为什么MST的边数总是V-1？

4. 如何处理带负权重的图？

5. 如果图不连通，如何找到最小生成森林？

7.2 编程问题

1. 实现支持删除边的动态MST

2. 找到所有可能的MST（如果存在权重相同的边）

3. 在有向图中找到最小树形图

4. 在流网络中应用MST算法

5. 并行化Kruskal算法

八、总结要点

8.1 核心记忆点

1. Kruskal：边排序 + 并查集，适合稀疏图

2. Prim：顶点扩展 + 优先队列，适合稠密图

3. 两者都是贪心算法，都能得到全局最优解

4. MST边数 = 顶点数 - 1

5. 时间复杂度都是O(E log V)级别

8.2 应用建议

• 小规模图：两种都可以，Prim实现更简单

• 大规模稀疏图：优先考虑Kruskal

• 需要频繁更新：Kruskal更容易维护

• 实时计算：Prim可以逐步输出结果

通过理解这两种算法的原理、实现和适用场景，可以灵活解决各种最小生成树相关问题。