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

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

深さ優先検索 (DFS) は、グラフ理論における古典的な検索アルゴリズムです。通常、次の目的で使用されます。グラフまたはツリートラバーサル問題を解決します。この記事では、Java を使用して深さ優先検索アルゴリズムを作成する方法を紹介し、具体的なコード例を示します。

1. アルゴリズム原理

深さ優先検索 (DFS) は、ノードから開始され、それ以上進めなくなるまでパスに沿って進み、その後、前のノードにロールバックします。 、別のパスを試してください。この検索方法は迷路の探索に似ており、まず開始点としてノードを選択し、訪問済みとしてマークし、その後、終点に到達するかすべてのノードを訪問し終わるまで、隣接するノードを再帰的に訪問します。

2. 実装手順

ステップ 1: グラフの構造を表すグラフ クラスを作成します。隣接リストまたは隣接行列を使用してグラフを表現できます。

class Graph {
    private int V; // 图的顶点数
    private LinkedList<Integer> adj[]; // 邻接表

    // 构造方法
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for(int i=0; i<v; ++i) {
            adj[i] = new LinkedList();
        }
    }

    // 添加边
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // 深度优先搜索
    void DFS(int v, boolean visited[]) {
        visited[v] = true; // 标记当前节点为已访问

        System.out.print(v + " "); // 打印当前节点

        Iterator<Integer> i = adj[v].listIterator();
        while(i.hasNext()) {
            int n = i.next();
            if(!visited[n]) {
                DFS(n, visited);
            }
        }
    }

    // 对图进行深度优先搜索
    void depthFirstSearch(int v) {
        boolean visited[] = new boolean[V]; // 用于记录节点是否已经访问过

        DFS(v, visited);
    }
}

ステップ 2: 深さ優先検索アルゴリズムの正しさを検証するテスト クラスを作成します。

class DFSAlgorithm {
    public static void main(String args[]) {
        Graph graph = new Graph(5); // 创建一个包含5个顶点的图

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);

        System.out.println("深度优先搜索结果：");
        graph.depthFirstSearch(0);
    }
}

3. 実行結果

深さ優先検索結果:
0 1 3 2 4

4. 概要

深さ優先検索アルゴリズムは、グラフ内のすべてのノードを走査できる一般的に使用されるグラフ アルゴリズムです。再帰により、深さ優先検索アルゴリズムを簡単に実装できます。上記のコードは、基本的な深さ優先検索アルゴリズムの例を示しており、実際のニーズに応じて変更および拡張できます。

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