Javaを使用して幅優先検索アルゴリズムを実装する方法

Java を使用して幅優先検索アルゴリズムを実装する方法

幅優先検索アルゴリズム (Breadth-First Search、BFS) は、一般的に使用される検索アルゴリズムです。グラフ理論では、グラフ内の 2 つのノード間の最短経路を見つけることができます。 BFS は、迷路内の最短経路の検索や Web クローラーなど、多くのアプリケーションで広く使用されています。

この記事では、Java 言語を使用して BFS アルゴリズムを実装する方法を紹介し、具体的なコード例を添付します。

まず、グラフ ノードを格納するためのクラスを定義する必要があります。このクラスには、ノードの値と他のノードとの関係が含まれます。サンプル コードは次のとおりです。

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

次に、BFS アルゴリズムを実装する関数を定義します。この関数は、開始ノードとターゲット ノードをパラメータとして受け取り、開始ノードからターゲット ノードまでの最短パスを返します。サンプル コードは次のとおりです。

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

上記のコードでは、キューを使用して各ノードを順番に処理します。まず開始ノードをキューに追加してから、ループに入ります。各ループ反復で、キュー内の最初のノードを取得し、それを訪問済み状態に設定します。次に、ノードがターゲット ノードであるかどうかを確認し、ターゲット ノードである場合は、パスを構築して戻ります。そうでない場合、ノードのすべての隣接ノードが走査され、未訪問の隣接ノードがキューに追加されます。ループはキューが空になるまで継続します。

最後に、buildPath 関数を呼び出して最短パスを構築します。 buildPath 関数はターゲット ノードから開始し、ノードの previous ポインタに沿ってトレースバックし、各ノードをパスに追加します。最後に、構築されたパスが返されます。

使用例は次のとおりです:

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

上記のコードは、単純な有向グラフを構築し、BFS アルゴリズムを使用してノード 1 からノード 5 までの最短パスを見つけます。最後に、最短パスをコンソールに出力します。

上記の例を通じて、Java 言語を使用して幅優先検索アルゴリズムを実装する方法を学び、具体的なコード例を示しました。この記事が BFS アルゴリズムの実装プロセスを理解するのに役立つことを願っています。

以上がJavaを使用して幅優先検索アルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。