プログラミング

Javaでの深さ優先探索

最終更新： 14/03/2025
1 分の読み

深さ優先探索（DFS）アルゴリズムは、グラフやツリーを探索するための重要な手法です。DFSは再帰的に実装されることが多く、スタックを使って明示的に実装することもできます。ここでは、DFSを「繰り返し」と「反復」に基づいて深く探求し、Javaでどのように実装するかについて詳しく説明します。

深さ優先探索（DFS）の基本概念

DFSは、スタートノードから始めて、そのノードに隣接するノードを一つずつ訪れ、訪れたノードからさらに深く探索を行っていく方法です。グラフ全体を探索するためには、すべてのノードにアクセスし、その隣接ノードを繰り返し調べる必要があります。この探索方法は、再帰を使うことが一般的です。

関連記事

深さ優先探索（DFS）のアルゴリズムのフロー

  1. スタートノードを決定：探索を始めるノードを選びます。
  2. 訪れたノードを記録：ノードを訪れたことを記録します。訪問済みのノードを再度訪れないようにするため、セットやリストを使うことが一般的です。
  3. 隣接ノードの探索：現在のノードに隣接するノードを再帰的に訪れ、深さ方向に進んでいきます。
  4. 終点に達するか、すべての隣接ノードを訪れるまで繰り返す：すべての隣接ノードを訪問したら、再帰的に前のノードに戻り、さらに探索を続けます。

Javaでの深さ優先探索（DFS）の実装方法

DFSをJavaで実装する際には、まずグラフの表現方法を考える必要があります。ここでは、隣接リストを使ってグラフを表現し、再帰的にDFSを実装します。

グラフの表現

まず、グラフを隣接リストで表現します。隣接リストは、各ノードの隣接ノードをリストで保持する方法です。例えば、グラフが以下のような形で与えられているとします：

0 → 1, 2
1 → 0, 3, 4
2 → 0, 4
3 → 1
4 → 1, 2

これを隣接リストで表現すると次のようになります。

java
import java.util.*;

public class Graph {
    private Map> adjList;

    public Graph(int vertices) {
        adjList = new HashMap<>();
        for (int i = 0; i < vertices; i++) {
            adjList.put(i, new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
        adjList.get(v).add(u);  // 無向グラフの場合
    }

    public List getAdjVertices(int v) {
        return adjList.get(v);
    }
}

DFSの再帰的実装

DFSの再帰的な実装では、探索するノードを一つずつ処理していきます。以下は再帰的にDFSを実行する方法です。

java
public class DFS {
    private Graph graph;
    private Set visited;

    public DFS(Graph graph) {
        this.graph = graph;
        this.visited = new HashSet<>();
    }

    public void dfsRecursive(int start) {
        visited.add(start);
        System.out.print(start + " ");  // 訪れたノードを表示

        // 隣接ノードを再帰的に探索
        for (int neighbor : graph.getAdjVertices(start)) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(neighbor);
            }
        }
    }
}

DFSの反復的実装

次に、DFSを反復的に実装する方法を見てみましょう。再帰を使わずに、スタックを使用してノードを探索していきます。

java
public class DFSIterative {
    private Graph graph;
    private Set visited;

    public DFSIterative(Graph graph) {
        this.graph = graph;
        this.visited = new HashSet<>();
    }

    public void dfsIterative(int start) {
        Stack stack = new Stack<>();
        stack.push(start);
        
        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (!visited.contains(current)) {
                visited.add(current);
                System.out.print(current + " ");  // 訪れたノードを表示
            }

            // 隣接ノードをスタックに追加
            for (int neighbor : graph.getAdjVertices(current)) {
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

実行例

以下は、DFSを実行するためのメインクラスの例です。

java
public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 4);

        // 再帰的DFS
        DFS dfs = new DFS(graph);
        System.out.println("再帰的DFS:");
        dfs.dfsRecursive(0);

        // 反復的DFS
        DFSIterative dfsIterative = new DFSIterative(graph);
        System.out.println("\n反復的DFS:");
        dfsIterative.dfsIterative(0);
    }
}

実行結果

makefile
再帰的DFS:
0 1 3 4 2 
反復的DFS:
0 2 4 1 3

まとめ

深さ優先探索（DFS）は、グラフやツリーの探索において非常に重要なアルゴリズムです。再帰的な方法と反復的な方法の両方を理解することは、DFSを効率的に使用するために重要です。再帰を使う方法はコードが簡潔になりますが、反復的な方法はスタックを使用して明示的にノードを管理できるため、再帰的な制限を回避できます。どちらの方法もグラフの探索において強力なツールです。

最終更新： 14/03/2025
1 分の読み
Back to top button