How to implement breadth first search algorithm using java

How to use Java to implement the breadth-first search algorithm

The breadth-first search algorithm (Breadth-First Search, BFS) is a commonly used search algorithm in graph theory, which can Find the shortest path between two nodes in the graph. BFS is widely used in many applications, such as finding the shortest path in a maze, web crawlers, etc.

This article will introduce how to use Java language to implement the BFS algorithm, and attach specific code examples.

First, we need to define a class for storing graph nodes. This class contains the value of the node and its relationship with other nodes. The sample code is as follows:

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

Next, we define a function to implement the BFS algorithm. This function accepts a start node and a target node as parameters and returns the shortest path from the start node to the target node. The sample code is as follows:

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

In the above code, we use a queue to process each node in turn. First add the starting node to the queue and then enter the loop. On each loop iteration, we take the first node in the queue and set it to the visited state. Then check if the node is the target node, if so, build the path and return. If not, all neighbor nodes of the node are traversed and unvisited neighbor nodes are added to the queue. The loop continues until the queue is empty.

Finally, we call the buildPath function to build the shortest path. The buildPath function starts from the target node, traces back along the node's previous pointer, and adds each node to the path. Finally, the constructed path is returned.

Usage examples are as follows:

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

The above code builds a simple directed graph and uses the BFS algorithm to find the shortest path from node 1 to node 5. Finally, output the shortest path to the console.

Through the above examples, we learned how to use the Java language to implement the breadth-first search algorithm and provided specific code examples. I hope this article can help you understand the implementation process of the BFS algorithm.

The above is the detailed content of How to implement breadth first search algorithm using java. For more information, please follow other related articles on the PHP Chinese website!