Java的Prim算法知识点（含面试大厂题和源码）

Prim算法是一种用于求解加权无向图的最小生成树问题的贪心算法。最小生成树是指在一个加权无向图中，连接所有顶点的权值最小的树。Prim算法通过逐步增加新的边和顶点来构建最小生成树。以下是Prim算法的一些关键知识点：

1. 算法概述

Prim算法从图中的任意一个顶点开始，初始化一个优先队列（通常是最小堆），用于存储所有连接已选顶点和未选顶点的边。每次从优先队列中取出权值最小的边，并将其对应的顶点加入到最小生成树中。重复这个过程，直到所有顶点都被包含在最小生成树中。

2. 算法步骤

1. 选择图中的任意一个顶点作为起始点，将其加入到最小生成树集合中。
2. 将所有与当前最小生成树集合中的顶点相连的边加入到优先队列中。
3. 从优先队列中取出权值最小的边（即堆顶元素），如果这条边连接的顶点不在最小生成树集合中，则将该顶点和边加入到最小生成树中，并将这条边的所有相邻边加入到优先队列中。
4. 重复步骤3，直到所有顶点都被加入到最小生成树中。

3. 数据结构

Prim算法主要使用了优先队列（最小堆）这一数据结构来维护边的权值。优先队列能够在O(log n)的时间复杂度内取出权值最小的边，这是算法效率的关键。

4. 时间复杂度

Prim算法的时间复杂度取决于优先队列的实现。使用二叉堆作为优先队列时，算法的时间复杂度为O(E log V)，其中E是边的数量，V是顶点的数量。如果使用斐波那契堆作为优先队列，时间复杂度可以进一步降低到O(E + V log V)。

5. 空间复杂度

Prim算法的空间复杂度主要取决于存储边和顶点的数据结构。通常，算法需要额外的空间来存储已选择的边和优先队列中的边，空间复杂度为O(E)。

6. 算法适用性

Prim算法适用于稠密图，即边的数量接近顶点数量的平方的图。在稀疏图中，Kruskal算法可能是一个更好的选择，因为它的时间复杂度与边的数量有关，而不与顶点的数量有关。

7. 算法优化

可以通过优化数据结构来提高Prim算法的效率。例如，使用斐波那契堆作为优先队列可以减少算法的时间复杂度。此外，如果图的边数不是很大，可以考虑使用动态规划或其他方法来优化算法。

8. 实现示例

以下是使用Java实现Prim算法的一个简单示例：

import java.util.*;

public class PrimMST {
    private static class Edge implements Comparable<Edge> {
        int from, to, weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public int compareTo(Edge other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

    public List<Edge> primMST(int[][] graph, int n) {
        boolean[] visited = new boolean[n];
        List<Edge> mst = new ArrayList<>();
        PriorityQueue<Edge> pq = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                pq.offer(new Edge(i, j, graph[i][j]));
            }
        }

        int totalWeight = 0;
        while (!pq.isEmpty()) {
            Edge currentEdge = pq.poll();
            if (!visited[currentEdge.from] && !visited[currentEdge.to]) {
                mst.add(currentEdge);
                totalWeight += currentEdge.weight;
                visited[currentEdge.from] = true;
                visited[currentEdge.to] = true;

                // 移除已经访问过的顶点的边
                for (Edge edge : pq) {
                    if (edge.from == currentEdge.from || edge.to == currentEdge.to) {
                        pq.remove(edge);
                    }
                }
            }
        }

        return mst;
    }

    public static void main(String[] args) {
        PrimMST primMST = new PrimMST();
        int n = 4;
        int[][] graph = {{0, 1, 0, 0},
                        {1, 0, 1, 1},
                        {0, 1, 0, 1},
                        {0, 1, 1, 0}};
        List<Edge> result = primMST.primMST(graph, n);
        System.out.println("Total weight of MST: " + result.stream().mapToInt(Edge::getWeight).sum());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

通过掌握这些知识点，你可以更好地理解和实现Prim算法，从而在面试中解决相关的图论问题。

题目 1：字符串中的第一个唯一字符

问题描述：给定一个字符串，找到字符串中第一个不重复的字符。

解决方案：使用哈希表记录每个字符出现的次数，然后遍历字符串，找到第一个计数为1的字符。

Java 源码：

public class FirstUniqueChar {
    public char firstUniqChar(String s) {
        if (s == null || s.isEmpty()) {
            return '#';
        }
        int[] count = new int[256]; // 假设字符集大小为256
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (count[s.charAt(i)] == 1) {
                return s.charAt(i);
            }
        }
        return '#';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题目 2：有效的括号

问题描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

解决方案：使用栈数据结构，遇到左括号就入栈，遇到右括号就出栈，如果栈为空或者最后栈中还有元素，则字符串无效。

Java 源码：

import java.util.Stack;

public class ValidParentheses {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char last = stack.pop();
                if ((c == ')' && last != '(') || (c == '}' && last != '{') || (c == ']' && last != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

题目 3：合并两个有序数组

问题描述：给定两个有序整数数组 nums1 和 nums2，在不使用额外空间的情况下，将 nums2 合并到 nums1 中。

解决方案：从两个数组的末尾开始比较元素大小，将较大的元素放到 nums1 的末尾，直到 nums2 被完全合并。

Java 源码：

public class MergeSortedArray {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1; // nums1 的最后一个元素的索引
        int p2 = n - 1; // nums2 的最后一个元素的索引
        int p = m + n - 1; // 合并后数组的最后一个元素的索引

        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p--] = nums1[p1--];
            } else {
                nums1[p--] = nums2[p2--];
            }
        }

        while (p2 >= 0) {
            nums1[p--] = nums2[p2--];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这些题目涵盖了哈希表、栈和数组操作等常见的数据结构和算法知识点，是面试中常见的问题类型。在准备面试时，理解和掌握这些问题的解决方法对于成功通过技术面试至关重要。