Javaで学ぶ「グラフ探索アルゴリズム」（後半）
前半では、グラフという「点と線の集合」を隣接リストで表現しながら、 DFS（深さ優先探索）と BFS（幅優先探索）の動き方とコードを丁寧に追いました。 後半では、そこから一歩進んで「最短経路」「重み付きグラフ」「計算量」「セキュリティ」という、 実務でグラフ探索を使いこなすうえで欠かせないテーマを掘り下げていきます。
グラフ探索は、単なるアルゴリズムの知識ではなく、 ネットワーク、ルーティング、依存関係解析、SNS、セキュリティ診断などに直結する「武器」です。
BFSで考える「最短経路」の意味
まず、「最短経路」を一番シンプルな形で考えてみます。 前半で扱った BFS は、「距離の近い順にノードを訪問する」探索でした。 この性質は、そのまま「最短経路」に直結します。
辺に重みがない、つまり「一歩進むコストがすべて同じ」のグラフでは、 BFSを使うことで「スタートから各ノードまでの最小ステップ数」を自然に求めることができます。
例えば、次のようなグラフを考えます。
A から B と C に行ける B から D に行ける C から D に行ける
A から D までの最短経路は、 A → B → D または A → C → D で、どちらも 2 ステップです。
この「ステップ数」を求めるには、BFSで「距離」を記録しながら探索すればよいことになります。
Javaで書く「BFSによる最短ステップ数」
距離を記録する BFS のコードを見てみましょう。
import java.util.*;
public class ShortestPathUnweighted {
public static Map<String, Integer> bfsDistance(Map<String, List<String>> graph, String start) {
Map<String, Integer> distance = new HashMap<>();
Queue<String> queue = new ArrayDeque<>();
distance.put(start, 0);
queue.add(start);
while (!queue.isEmpty()) {
String node = queue.poll();
int dist = distance.get(node);
List<String> neighbors = graph.getOrDefault(node, Collections.emptyList());
for (String next : neighbors) {
if (!distance.containsKey(next)) {
distance.put(next, dist + 1);
queue.add(next);
}
}
}
return distance;
}
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("D"));
graph.put("C", Arrays.asList("D"));
graph.put("D", Collections.emptyList());
Map<String, Integer> dist = bfsDistance(graph, "A");
System.out.println("Distance to D: " + dist.get("D")); // 2
}
}
ここで重要なのは、距離を Map<String, Integer> で管理している点です。 スタートノードの距離を 0 とし、隣接ノードの距離を「今の距離 + 1」として記録していきます。 まだ距離が記録されていないノードだけをキューに追加することで、 同じノードを何度も処理することを防いでいます。
この仕組みにより、「最初に距離が記録されたときの値」がそのノードへの最短ステップ数になります。 BFSは「近い順に広がる」ため、後からより短い経路が見つかることはありません。
重み付きグラフという現実的な世界
現実の問題では、「すべての辺のコストが同じ」ということはほとんどありません。 道路なら距離や時間が違い、ネットワークなら帯域や遅延が違い、 セキュリティの世界なら「通るのが危険な経路」と「安全な経路」が存在します。
こうした「辺ごとにコストが違う」グラフを扱うのが、重み付きグラフです。
Javaで重み付きグラフを表現する一つの方法は、 「ノード → 辺の一覧」という形で持つことです。
class Edge {
String to;
int cost;
Edge(String to, int cost) {
this.to = to;
this.cost = cost;
}
}
Map<String, List<Edge>> graph = new HashMap<>();
graph.put("A", Arrays.asList(new Edge("B", 5), new Edge("C", 2)));
graph.put("B", Arrays.asList(new Edge("D", 1)));
graph.put("C", Arrays.asList(new Edge("D", 7)));
graph.put("D", Collections.emptyList());
この例では、A から B へはコスト 5、A から C へはコスト 2、 B から D へはコスト 1、C から D へはコスト 7 となっています。
A から D への最短経路を考えると、 A → B → D のコストは 5 + 1 = 6 A → C → D のコストは 2 + 7 = 9 となり、A → B → D が最短になります。
ここで重要なのは、「ステップ数」ではなく「合計コスト」が問題になるという点です。 このとき、単純な BFS では最短経路を求めることができません。
Dijkstraアルゴリズムの直感：一番安いルートから確定していく
重み付きグラフの最短経路を求める代表的なアルゴリズムが、Dijkstra（ダイクストラ）法です。 このアルゴリズムの直感は、「今わかっている中で一番安いノードから確定していく」というものです。
スタートノードのコストを 0 とし、 他のノードのコストを「まだ無限大」としておきます。 そこから次のように進めます。
まだ確定していないノードの中から「現在のコストが最小のノード」を選ぶ そのノードから出ている辺をたどり、隣接ノードのコストを更新する これを繰り返すことで、すべてのノードへの最短コストが確定していく
この「最小コストのノードから確定していく」という考え方が、Dijkstraの核心です。
Javaで書くシンプルなDijkstraアルゴリズム
優先度付きキュー（PriorityQueue）を使うことで、 「現在のコストが最小のノード」を効率よく取り出すことができます。
import java.util.*;
class Edge {
String to;
int cost;
Edge(String to, int cost) {
this.to = to;
this.cost = cost;
}
}
public class DijkstraExample {
public static Map<String, Integer> dijkstra(Map<String, List<Edge>> graph, String start) {
Map<String, Integer> dist = new HashMap<>();
for (String node : graph.keySet()) {
dist.put(node, Integer.MAX_VALUE);
}
dist.put(start, 0);
PriorityQueue<String> pq = new PriorityQueue<>(Comparator.comparingInt(dist::get));
pq.add(start);
while (!pq.isEmpty()) {
String node = pq.poll();
int currentDist = dist.get(node);
List<Edge> edges = graph.getOrDefault(node, Collections.emptyList());
for (Edge e : edges) {
int newDist = currentDist + e.cost;
if (newDist < dist.get(e.to)) {
dist.put(e.to, newDist);
pq.add(e.to);
}
}
}
return dist;
}
public static void main(String[] args) {
Map<String, List<Edge>> graph = new HashMap<>();
graph.put("A", Arrays.asList(new Edge("B", 5), new Edge("C", 2)));
graph.put("B", Arrays.asList(new Edge("D", 1)));
graph.put("C", Arrays.asList(new Edge("D", 7)));
graph.put("D", Collections.emptyList());
Map<String, Integer> dist = dijkstra(graph, "A");
System.out.println("Cost to D: " + dist.get("D")); // 6
}
}
このコードで深掘りしたいポイントは三つあります。
一つ目は、距離 dist を「最初はすべて最大値」にしている点です。 これにより、「まだ到達していないノード」は無限大のコストとして扱われます。
二つ目は、PriorityQueue を使って「現在の距離が最小のノード」を取り出している点です。 これが、Dijkstraの「一番安いノードから確定していく」という考え方を支えています。
三つ目は、隣接ノードの距離を newDist < dist.get(e.to) のときだけ更新している点です。 これにより、「より安い経路が見つかったときだけ」距離が更新されます。
この仕組みを通して、 スタートから各ノードへの最短コストが効率よく求まります。
計算量の視点から見るDFS・BFS・Dijkstra
グラフ探索アルゴリズムを実務で使うとき、 計算量の感覚は非常に重要です。
DFSとBFSは、基本的に「ノード数＋辺の数」に比例した時間で動きます。 ノード数を V、辺の数を E とすると、 計算量はおおよそ O(V + E) です。
Dijkstraは、優先度付きキューを使うことで 計算量は O((V + E) log V) 程度になります。 グラフが大きくなると、log V の要素が効いてきますが、 それでも現実的なサイズのグラフに対して十分高速です。
この「増え方の違い」を意識できると、 どのアルゴリズムを選ぶべきかを判断しやすくなります。
セキュリティの視点から見るグラフ探索
グラフ探索は、セキュリティの世界でもよく使われます。 ネットワークの到達可能性、依存関係の解析、権限の伝播などを調べるとき、 DFSやBFS、Dijkstraがそのまま登場します。
同時に、グラフ探索は攻撃の入口にもなり得ます。
外部入力から渡された巨大なグラフに対して、 無制限に DFS や BFS を行うと、 膨大な時間とメモリを消費し、サービスが停止する可能性があります。
また、重み付きグラフに対して Dijkstra を実行する場合、 攻撃者が「極端に多くのノードと辺」を持つ入力を送ることで、 計算量を意図的に増やすことができます。
安全な設計としては、 グラフのノード数や辺の数に上限を設けること、 深さや距離に制限を設けること、 異常な構造（自己ループや極端な多重辺）を事前にフィルタリングすることが重要になります。
グラフ探索は強力な道具であると同時に、 「どこまで探索するか」をきちんと決めないと危険な処理にもなり得ます。
実務でのグラフ探索アルゴリズムの活用イメージ
グラフ探索アルゴリズムは、 抽象的な理論ではなく、実務でそのまま使える技術です。
SNSで「友達の友達」をたどる処理は BFS そのものです。 依存関係の解析やビルド順の決定には、グラフとDFSが使われます。 ネットワークのルーティングや経路選択には、Dijkstraがそのまま登場します。 セキュリティ診断では、「どの経路で権限が伝播するか」をグラフとして解析します。
こうした場面で、 「グラフをどう表現するか」 「DFSとBFSのどちらを使うか」 「重み付きならDijkstraを使うべきか」 といった判断ができることは、 エンジニアとしての設計力そのものです。
後半のまとめ
後半では、グラフ探索アルゴリズムを一段深く理解するために
BFSによる最短ステップ数の求め方 重み付きグラフの表現と「コスト」という概念 Dijkstraアルゴリズムの直感とJavaでの実装 DFS・BFS・Dijkstraの計算量の違い グラフ探索とセキュリティの関係 実務でのグラフ探索アルゴリズムの活用イメージ
を整理しました。
グラフ探索を理解すると、「つながり」を扱う問題に対して 自分の頭でアルゴリズムを設計できるようになります。 それは、単なるコードのテクニックではなく、 システム全体を見渡す設計力につながっていきます。