Mímisbrunnr知恵の泉

← ネットワーク科学 一覧

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：次数・道・連結成分　|　関連：近接中心性・媒介中心性・ランダムウォークと拡散の数理

要点（BLUF）

概念：すべてのノードを系統的に巡る

「このノードからどこまで行けるか」「最短で何歩か」を知るには、グラフを系統的に歩く必要があります。その2大流儀が BFS と DFS。違いは「次にどこへ進むか」という管理だけ — BFS はキュー（先入れ先出し）、DFS はスタック（後入れ先出し／再帰）です。この小さな違いが、得られる情報の質を変えます。

アルゴリズムの定義

BFS：始点 ss を層0とし、層 ℓ\ell のノードの未訪問の隣人を層 ℓ+1\ell+1 とする。キューを使い、近いノードから順に展開します。結果として ss から各ノードまでの**最短距離（ホップ数）**が得られます。

DFS：始点から1つの隣人へ深く潜り、行き止まりになったら直前の分岐へ戻る（バックトラック）。スタックまたは再帰で実装します。訪問の「行きがけ順（preorder）」「帰りがけ順（postorder）」が、閉路検出や有向グラフのトポロジカルソートに使われます。

両者とも各ノードを1回、各エッジを定数回見るので計算量は O(n+m)O(n+m)。

コードで確認

import networkx as nx

G = nx.Graph()
G.add_edges_from([(0,1),(0,2),(1,3),(2,3),(3,4),(2,5)])

# BFS：始点0から近い順に
print("BFS エッジ順:", list(nx.bfs_edges(G, 0)))
print("BFS 各ノードの層:", nx.single_source_shortest_path_length(G, 0))

# DFS：深く潜って戻る
print("DFS エッジ順:", list(nx.dfs_edges(G, 0)))
print("DFS 訪問順(preorder):", list(nx.dfs_preorder_nodes(G, 0)))

実行結果：

BFS エッジ順: [(0, 1), (0, 2), (1, 3), (2, 5), (3, 4)]
BFS 各ノードの層: {0: 0, 1: 1, 2: 1, 3: 2, 5: 2, 4: 3}
DFS エッジ順: [(0, 1), (1, 3), (3, 2), (2, 5), (3, 4)]
DFS 訪問順(preorder): [0, 1, 3, 2, 5, 4]

BFS は層ごとに広がるので、ノード4は「層3＝始点から3ホップ」とすぐ分かります。DFS は 0→1→3→2→5 と一気に深く潜ってから、行き止まりで戻って4を拾う。同じグラフでも訪問順がまったく違うことに注目してください。

訪問順の違い

graph TD
    subgraph BFS["BFS: 層で広がる"]
        b0["0 (層0)"] --> b1["1 (層1)"]
        b0 --> b2["2 (層1)"]
        b1 --> b3["3 (層2)"]
        b2 --> b5["5 (層2)"]
        b3 --> b4["4 (層3)"]
    end

BFS の探索木では「親→子」のエッジが必ず最短路を与えます。DFS の探索木は細長く伸びやすく、深い構造の発見に向きます。

数式の直観的意味

BFS が最短路を与えるのは、「層 ℓ\ell をすべて出し切ってから層 ℓ+1\ell+1 に進む」という規律のおかげです。あるノードに初めて到達したとき、それより短い経路は既に調べ尽くされているので、その到達が最短だと保証されます。これが「キュー（FIFO）＝近い順」という対応の本質です。DFS の LIFO は逆に「最後に見つけた道を最優先」なので、距離は保証されません。

⚠️ よくある誤解・落とし穴

対応シミュレーション

本文のコードがそのまま検証用です。媒介中心性は内部で全点対の BFS/最短路を回します（近接中心性・媒介中心性）。

関連