当前位置：首页 > Java

java如何优先遍历

2026-03-24 03:30:41Java

优先遍历的实现方法

在Java中实现优先遍历（通常指优先队列或带权图的遍历）可以通过多种方式完成。以下是常见的实现方法：

使用PriorityQueue实现优先遍历

PriorityQueue是Java集合框架中的一个类，基于优先级堆实现。默认情况下，元素按自然顺序排序，也可以通过Comparator自定义排序规则。

java如何优先遍历

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。

java如何优先遍历

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);
        }
    }
}