Java实现优先队列式广度优先搜索算法的示例代码

实现优先队列式广度优先搜索（Priority Queue-based BFS）算法需要遵循以下几个步骤：

Step 1：初始化

首先，我们需要初始化一个待访问节点的优先队列priority queue、一个已访问节点的哈希表visited map、以及图的邻接表adjacent list。将源节点加入到priority queue中，并将visited map置为true。

PriorityQueue<Node> pq = new PriorityQueue<>();
Map<Node, Boolean> visited = new HashMap<>();
Map<Node, List<Node>> adj = new HashMap<>();
pq.offer(sourceNode);
visited.put(sourceNode, true);

Step 2：广度优先遍历

接下来，我们可以开始从priority queue中取出最高优先级的节点，检查它是否为目标节点，如果是则直接返回结果；如果不是，则将它的所有邻居节点加入到priority queue，并将它们在visited map中标记为已访问。这个过程就是广度优先遍历的核心算法。

while (!pq.isEmpty()) {
    Node currNode = pq.poll();
    if (currNode == targetNode) {
        return true; // 找到目标节点，直接返回true
    }
    List<Node> neighbors = adj.get(currNode);
    for (Node neighbor : neighbors) {
        if (!visited.containsKey(neighbor)) { // 如果邻居节点没有被访问过
            visited.put(neighbor, true);
            pq.offer(neighbor); // 加入到优先队列中
        }
    }
}

Step 3：构建图的邻接表

最后，我们需要构建图的邻接表，以便进行广度优先遍历。下面是一个简单的例子，展示了如何将节点之间的联系表达为邻接表。

class Node {
    int val;
    List<Node> neighbors;
}
Map<Node, List<Node>> adj = new HashMap<>();
for (Node node : nodeList) {
    adj.putIfAbsent(node, new ArrayList<>());
    for (Node neighbor : node.neighbors) {
        adj.get(node).add(neighbor);
    }
}

示例1

我们可以使用Priority Queue-based BFS算法来解决Kth Smallest Element in a Sorted Matrix这道题目。该题目要求我们在一个二维矩阵中找到第K小的数，可以将该矩阵看做一个有序矩阵。我们可以从矩阵左上角开始，按行向右、按列向下遍历矩阵，并将每个数加入到priority queue中。这样，可以保证队列中的数总是有序的，可以快速找到第K小的数。

public int kthSmallest(int[][] matrix, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // 大根堆
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            pq.offer(matrix[i][j]);
            if (pq.size() > k) {
                pq.poll(); // 只保留前K小的数
            }
        }
    }
    return pq.peek();
}

示例2

我们可以使用Priority Queue-based BFS算法来解决Dijkstra algorithm这道题目。该题目要求我们求解从源节点到目标节点的最短路径，可以将每个节点看做图中的一个顶点，将它们之间的距离看做权重。我们可以使用Priority Queue-based BFS算法来查找从源节点到目标节点的最短路径，过程中使用visited map来记录已访问的节点，通过邻接表来存储节点之间的距离。

public int dijkstra(int[][] edges, int sourceNode, int targetNode) {
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 小根堆
    Map<Integer, List<int[]>> adj = new HashMap<>();
    Map<Integer, Integer> dist = new HashMap<>();
    pq.offer(new int[]{sourceNode, 0});
    dist.put(sourceNode, 0);
    for (int[] edge : edges) {
        adj.putIfAbsent(edge[0], new ArrayList<>());
        adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
    }
    while (!pq.isEmpty()) {
        int[] currNode = pq.poll();
        if (currNode[0] == targetNode) {
            return dist.get(currNode[0]); // 找到目标节点，返回最短距离
        }
        if (!adj.containsKey(currNode[0])) {
            continue;
        }
        for (int[] neighbor : adj.get(currNode[0])) {
            int newDist = currNode[1] + neighbor[1];
            if (!dist.containsKey(neighbor[0]) || newDist < dist.get(neighbor[0])) {
                dist.put(neighbor[0], newDist);
                pq.offer(new int[]{neighbor[0], newDist});
            }
        }
    }
    return -1;
}