java如何优先遍历
优先遍历的实现方法
在Java中实现优先遍历（通常指优先队列或带权图的遍历）可以通过多种方式完成。以下是常见的实现方法：
使用PriorityQueue实现优先遍历
PriorityQueue是Java集合框架中的一个类，基于优先级堆实现。默认情况下，元素按自然顺序排序，也可以通过Comparator自定义排序规则。
import java.util.PriorityQueue;
public class PriorityTraversal {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
pq.add(3);
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
}自定义Comparator实现特定优先级
当需要按照非自然顺序排序时，可以传递Comparator给PriorityQueue。
import java.util.Comparator;
import java.util.PriorityQueue;
public class CustomPriority {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
pq.add(5);
pq.add(1);
pq.add(3);
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
}图的优先遍历（如Dijkstra算法）
对于带权图的优先遍历，通常使用优先队列来选择当前最短路径节点。
import java.util.*;
class Node implements Comparable<Node> {
int vertex;
int distance;
public Node(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.distance, other.distance);
}
}
public class Dijkstra {
public void shortestPath(List<List<Node>> adj, int src) {
PriorityQueue<Node> pq = new PriorityQueue<>();
int[] dist = new int[adj.size()];
Arrays.fill(dist, Integer.MAX_VALUE);
pq.add(new Node(src, 0));
dist[src] = 0;
while (!pq.isEmpty()) {
Node current = pq.poll();
for (Node neighbor : adj.get(current.vertex)) {
if (dist[neighbor.vertex] > dist[current.vertex] + neighbor.distance) {
dist[neighbor.vertex] = dist[current.vertex] + neighbor.distance;
pq.add(new Node(neighbor.vertex, dist[neighbor.vertex]));
}
}
}
}
}使用TreeSet实现优先遍历
TreeSet是基于TreeMap实现的NavigableSet，可以保持元素有序。
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
TreeSet<Integer> ts = new TreeSet<>();
ts.add(5);
ts.add(1);
ts.add(3);
for (Integer num : ts) {
System.out.println(num);
}
}
}注意事项
- PriorityQueue不允许null元素
- PriorityQueue的迭代顺序不保证有序，只有通过poll/remove方法获取的元素才是有序的
- 对于自定义对象，需要实现Comparable接口或提供Comparator
- PriorityQueue的时间复杂度：插入和删除操作都是O(log n)
