Java를 사용하여 너비 우선 탐색 알고리즘을 구현하는 방법

class Node {
    int value;
    boolean visited;
    List<Node> neighbors;

    public Node(int value) {
        this.value = value;
        this.visited = false;
        this.neighbors = new ArrayList<>();
    }

    public void addNeighbor(Node neighbor) {
        neighbors.add(neighbor);
    }
}

public List<Node> bfs(Node start, Node target) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(start);

    while (!queue.isEmpty()) {
        Node current = queue.remove();
        current.visited = true;

        if (current == target) {
            // 找到目标节点，构建最短路径并返回
            return buildPath(target);
        }

        for (Node neighbor : current.neighbors) {
            if (!neighbor.visited) {
                queue.add(neighbor);
                neighbor.visited = true;
            }
        }
    }

    // 未找到目标节点，返回空列表
    return new ArrayList<>();
}

private List<Node> buildPath(Node target) {
    List<Node> path = new ArrayList<>();
    Node current = target;

    while (current != null) {
        path.add(0, current);
        current = current.previous;
    }

    return path;
}

Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);

node1.addNeighbor(node2);
node1.addNeighbor(node3);
node2.addNeighbor(node4);
node3.addNeighbor(node4);
node4.addNeighbor(node5);

List<Node> shortestPath = bfs(node1, node5);

// 输出最短路径
for (Node node : shortestPath) {
    System.out.print(node.value + " -> ");
}