Java | グラフ探索アルゴリズム

Java Java
スポンサーリンク

Javaで学ぶ「グラフ探索アルゴリズム」（前半）

グラフ探索アルゴリズムは、アルゴリズム学習の中でも「一段レベルが上がる」テーマです。 SNSの友達関係、道路の経路、依存関係、ネットワーク構造など、 現実世界の「つながり」を扱う場面はほぼすべてグラフで表現できます。

前半では、まずグラフとは何かを丁寧にほどき、 そのうえで代表的な探索アルゴリズムである DFS（深さ優先探索） と BFS（幅優先探索） を、 Javaコードと具体例を交えながらかみ砕いて解説していきます。 後半では、最短経路や重み付きグラフ、セキュリティ・パフォーマンスの観点まで踏み込みます。

グラフとは何かを「点と線」のイメージで理解する

グラフは、「点（ノード）と線（エッジ）の集合」です。 ノードは「もの」、エッジは「関係」を表します。

例えば、次のような関係を考えてみます。

A は B とつながっている A は C ともつながっている B は C とつながっている

これをグラフとして表現すると、 A, B, C がノードで、 A–B, A–C, B–C がエッジになります。

Javaでグラフを表現する最も基本的な方法は「隣接リスト」です。 これは、「ノード → つながっているノードの一覧」という形で表現する方法です。

import java.util.*;

Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("C"));
graph.put("C", Arrays.asList("A"));
Java

このコードでは、 A は B と C に、 B は C に、 C は A に つながっていることを表現しています。

重要なのは、「グラフは自由なつながりを表現できる」という点です。 ツリーのように「親は一つだけ」といった制約はなく、 ノード同士が好きなようにつながることができます。

グラフ探索とは何か：「つながりをたどる」アルゴリズム

グラフ探索アルゴリズムは、「あるノードからスタートして、つながりをたどる」ための手順です。 目的はさまざまですが、基本的には次のようなことをします。

どのノードに到達できるかを知りたい 特定のノードが存在するかを調べたい 最短経路を見つけたい（後半で扱う） 連結成分（つながっているグループ）を調べたい

この「つながりをたどる」ための基本的なアルゴリズムが、 DFS（深さ優先探索）と BFS（幅優先探索）です。

前半では、まずこの二つをしっかり理解することを目標にします。

DFS（深さ優先探索）を直感で理解する

DFS（Depth-First Search）は、「深く潜っていく」探索です。 あるノードからスタートして、 行けるところまで一気に深く進み、 行き止まりになったら戻って別の道を探します。

迷路を歩くときに、 「とりあえず一つの道をずっと進んで、行き止まりになったら戻る」 という歩き方をイメージすると分かりやすいです。

Javaで DFS を書くと、再帰が非常に自然に使えます。

import java.util.*;

public class DFSExample {

    public static void dfs(Map<String, List<String>> graph, String start, Set<String> visited) {
        if (visited.contains(start)) {
            return;
        }
        visited.add(start);
        System.out.println("Visit: " + start);

        List<String> neighbors = graph.getOrDefault(start, Collections.emptyList());
        for (String next : neighbors) {
            dfs(graph, next, visited);
        }
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("C"));
        graph.put("C", Arrays.asList("A"));

        Set<String> visited = new HashSet<>();
        dfs(graph, "A", visited);
    }
}
Java

このコードの重要なポイントを深掘りしてみます。

まず、visited という集合を使って「すでに訪れたノード」を記録しています。 これは、グラフに「ループ（A→C→A のような循環）」がある場合に 無限ループに陥らないために必須です。

次に、dfs メソッドが自分自身を呼び出していることに注目してください。 あるノードを訪れたら、その隣接ノードに対して同じ処理を行う、 という形になっています。

この「自分自身を呼び出すことで、つながりをたどる」構造が、 DFS の本質です。

DFS の動きを具体例で追ってみる

先ほどのグラフ

A → B, C B → C C → A

に対して、dfs(graph, "A", visited) を呼び出したときの動きを追ってみます。

最初に A を訪問 Visit: A と表示し、visited に A を追加 A の隣接ノード B と C を順番にたどる

まず B に対して dfs B を訪問 Visit: B と表示し、visited に B を追加 B の隣接ノード C をたどる

C に対して dfs C を訪問 Visit: C と表示し、visited に C を追加 C の隣接ノード A をたどる

A に対して dfs しかし、A はすでに visited にあるため、何もせず return

これで、A → B → C → A というループを 安全にたどり終えることができます。

このように、DFS は「深く潜っていく」動きをします。 ツリー探索や、 「すべてのパスを調べたい」ような場面で非常に役立ちます。

BFS（幅優先探索）を直感で理解する

BFS（Breadth-First Search）は、「横に広がっていく」探索です。 あるノードからスタートして、 まず「1歩で行けるノード」をすべて訪れ、 次に「2歩で行けるノード」を訪れ、 というように、距離の近い順に広がっていきます。

人の輪を広げるイメージで考えると分かりやすいです。 ある人からスタートして、その友達を全員たどり、 次に「友達の友達」をたどる、 というように広がっていきます。

BFS では、キュー（Queue）を使うのが定番です。

import java.util.*;

public class BFSExample {

    public static void bfs(Map<String, List<String>> graph, String start) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new ArrayDeque<>();

        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            String node = queue.poll();
            System.out.println("Visit: " + node);

            List<String> neighbors = graph.getOrDefault(node, Collections.emptyList());
            for (String next : neighbors) {
                if (!visited.contains(next)) {
                    visited.add(next);
                    queue.add(next);
                }
            }
        }
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("C"));
        graph.put("C", Arrays.asList("A"));

        bfs(graph, "A");
    }
}
Java

ここで重要なのは、 「キューに入れた順番でノードを取り出している」という点です。 これにより、「近いノードから順に」探索が進みます。

BFS の動きを具体例で追ってみる

同じグラフに対して、bfs(graph, "A") を呼び出したときの動きを追ってみます。

最初に A を visited に追加し、queue に入れる

queue から A を取り出す Visit: A と表示 A の隣接ノード B と C を調べる B と C は未訪問なので、visited に追加し、queue に入れる

次に queue から B を取り出す Visit: B と表示 B の隣接ノード C を調べる C はすでに visited にあるので、何もしない

次に queue から C を取り出す Visit: C と表示 C の隣接ノード A を調べる A はすでに visited にあるので、何もしない

queue が空になったので終了

このように、BFS は「距離 1 → 距離 2 → 距離 3 …」という順番で ノードを訪問していきます。

この性質により、 「最短経路を見つける」 「距離ごとの層を調べる」 といった場面で非常に強力です。

DFS と BFS の違いを直感で整理する

ここまでの内容を、直感的な違いとしてまとめておきます。

DFS は「深く潜る」探索です。 再帰と相性が良く、 ツリー構造や「すべてのパスを調べたい」場面に向いています。

BFS は「横に広がる」探索です。 キューを使い、 「距離の近い順」にノードを訪問します。 最短経路や「層ごとの構造」を調べたい場面に向いています。

どちらも「グラフをたどる」アルゴリズムですが、 動き方のイメージがまったく違います。

DFS は「一本の道をとことん」、 BFS は「輪を広げるように少しずつ」。

このイメージがつかめると、 どの場面でどちらを選ぶべきかが自然に見えてきます。

前半のまとめと後半への橋渡し

前半では、グラフ探索アルゴリズムの入り口として

グラフとは何か（点と線の集合、隣接リストでの表現） グラフ探索とは「つながりをたどる」アルゴリズムであること DFS（深さ優先探索）の基本と再帰による実装 DFS の動きを具体例で追うことで「深く潜る」イメージをつかむこと BFS（幅優先探索）の基本とキューによる実装 BFS の動きを具体例で追うことで「横に広がる」イメージをつかむこと DFS と BFS の違いを直感で整理すること

を丁寧に解説しました。

後半では、ここから一歩進んで

最短経路探索（BFS と Dijkstra の違い） 重み付きグラフの扱い方 グラフ探索とセキュリティ（DoS・深さ制限・入力検証） 実務でのグラフアルゴリズムの具体的な活用例

を、Javaコードとともに深掘りしていきます。

次へ
12
スポンサーリンク
タイトルとURLをコピーしました