はじめに
本記事ではグラフ探索アルゴリズムの基本概念として、代表的な DFS (Depth First Search) と BFS (Breadth First Search) を中心に解説していきます。さらに、Python のグラフライブラリ NetworkX を用いた実装例を紹介し、Google Colab 上で実際に手を動かしながら体験できるハンズオン形式で進めます。
この記事のゴール
- グラフ探索の基本概念（DFS, BFS）を理解する。
- NetworkX を使った DFS / BFS の実装方法を学ぶ。
- 探索アルゴリズムの活用シーンや実用例をイメージする。
- Google Colab を使って手を動かしながら学習する。
1. グラフ探索とは
グラフ とは、「頂点 (Node or Vertex) と辺 (Edge)」で構成されるデータ構造です。頂点どうしを結ぶ辺を辿ることで、情報のつながりや関係を表すことができます。
一方、グラフ探索 は、ある頂点から他の頂点へどのように移動・探索できるかを調べることを指します。代表的な探索方法が DFS (深さ優先探索) と BFS (幅優先探索) です。
1.1 DFS (深さ優先探索)
- 深さ を優先して探索を進める。
- ある頂点から始め、行けるところまで どんどん奥に進む イメージ。
- スタック (stack) や再帰 (recursion) を用いて実装されることが多い。
1.2 BFS (幅優先探索)
- 幅 を優先して探索を進める。
- ある頂点から始め、同じ距離 (辺の数) にある頂点をすべて探索してから、次の距離へ移っていくイメージ。
- キュー (queue) を用いて実装されることが多い。
2. 活用シーン例
-
最短経路探索
BFS は辺の重みがすべて同じ時に最短経路を求める際に便利。地図上での移動距離（等コスト）や迷路探索などで利用。 -
到達可能性の判定
DFS/BFS を使い、ある頂点から別の頂点へ到達できるか調べる。ソーシャルグラフやネットワーク解析など。 -
連結成分の分割
グラフが複数の連結成分に分かれている場合に、それぞれどの頂点が属しているかを調べる。
3. Google Colab でハンズオン
以下の手順で Google Colab 上で DFS/BFS を体験することができます。
- Google Colab にアクセス
- 新しい Python ノートブックを開く
- 次のコードを順番に実行していく
3.1 ライブラリのインストールとインポート
# NetworkX がインストールされていない場合はコメントアウトを外す
# !pip install networkx
import networkx as nx
import matplotlib.pyplot as plt
# notebook 内でグラフを表示するためのおまじない
%matplotlib inline
3.2 グラフの生成
まずは簡単な有向グラフ (または無向グラフ) を作成します。以下では無向グラフを例にします。
# 無向グラフ G を作成
G = nx.Graph()
# 頂点(ノード)の追加
G.add_nodes_from([1, 2, 3, 4, 5])
# 辺(エッジ)の追加
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 4)]
G.add_edges_from(edges)
# グラフの可視化
pos = nx.spring_layout(G, seed=42) # 描画のレイアウトを固定
nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray')
plt.show()
3.3 DFS / BFS の基本実装（NetworkX の関数を使わない場合）
3.3.1 DFS の実装例
再帰を使った DFS の実装例です。
visited = set()
def dfs(graph, start):
visited.add(start)
print(start, end=" ")
# グラフ上で隣接するノードを探索
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor)
# 実行
start_node = 1
print("DFS order:")
dfs(G, start_node)
3.3.2 BFS の実装例
キューを使った BFS の実装例です。
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
current = queue.popleft()
print(current, end=" ")
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 実行
start_node = 1
print("
BFS order:")
bfs(G, start_node)
3.4 NetworkX による実装
NetworkX には標準で DFS / BFS に関連する関数がいくつか用意されています。たとえば、以下のように nx.dfs_preorder_nodes() や nx.bfs_tree() などを使うことで、より手軽に探索結果を取得できます。
# DFS (先行順) の探索順序を取得
dfs_result = list(nx.dfs_preorder_nodes(G, source=1))
print("NetworkX DFS preorder:", dfs_result)
# BFS の探索木を取得
bfs_tree = nx.bfs_tree(G, source=1)
print("NetworkX BFS tree edges:", list(bfs_tree.edges()))
4. まとめと今後の展開
- DFS/BFS はグラフ探索アルゴリズムの基本となる。
- DFS は木構造の探索やバックトラッキングに便利、BFS は最短経路 (単純重み付き) の探索やレイヤーごとの分割に便利。
- NetworkX を使えば、少ないコードで探索が可能。
- 今後は、最短経路探索 (Dijkstra, Bellman-Ford, Floyd-Warshall など) や、さらに応用的なグラフアルゴリズムを扱っていく予定です。
参考
最後までお読みいただき、ありがとうございます。ぜひ Google Colab 上でコードを実行しながら、DFS/BFS の挙動を体感してみてください。
実装例: ノートブック
{
"cells": [
{
"cell_type": "markdown",
"id": "d17bb0dd",
"metadata": {},
"source": [
"# Graph アルゴリズム入門 (1)：DFS/BFS ハンズオン\n",
"このノートブックでは、DFS と BFS を Google Colab 上で実装し、その挙動を確認します。"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "620caf51",
"metadata": {},
"outputs": [],
"source": [
"# 必要なライブラリをインストール\n",
"# NetworkX がインストールされていない場合に以下のコメントを外して実行してください\n",
"# !pip install networkx\n",
"\n",
"import networkx as nx\n",
"import matplotlib.pyplot as plt\n",
"from collections import deque\n",
"%matplotlib inline"
]
},
{
"cell_type": "markdown",
"id": "ea32d35f",
"metadata": {},
"source": [
"## グラフの生成\n",
"以下では簡単な無向グラフを作成します。"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "20230b27",
"metadata": {},
"outputs": [],
"source": [
"# 無向グラフ G を作成\n",
"G = nx.Graph()\n",
"\n",
"# 頂点(ノード)の追加\n",
"G.add_nodes_from([1, 2, 3, 4, 5])\n",
"\n",
"# 辺(エッジ)の追加\n",
"edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 4)]\n",
"G.add_edges_from(edges)\n",
"\n",
"# グラフの可視化\n",
"pos = nx.spring_layout(G, seed=42) # レイアウトを固定\n",
"nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "19e58ba3",
"metadata": {},
"source": [
"## DFS の実装\n",
"再帰を使った DFS の実装例です。"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "165a796d",
"metadata": {},
"outputs": [],
"source": [
"visited = set()\n",
"\n",
"def dfs(graph, start):\n",
" visited.add(start)\n",
" print(start, end=\" \")\n",
" for neighbor in graph[start]:\n",
" if neighbor not in visited:\n",
" dfs(graph, neighbor)\n",
"\n",
"# 実行\n",
"start_node = 1\n",
"print(\"DFS order:\")\n",
"dfs(G, start_node)"
]
},
{
"cell_type": "markdown",
"id": "6bd0b9e9",
"metadata": {},
"source": [
"## BFS の実装\n",
"キューを使った BFS の実装例です。"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "75ee5688",
"metadata": {},
"outputs": [],
"source": [
"def bfs(graph, start):\n",
" visited = set([start])\n",
" queue = deque([start])\n",
"\n",
" while queue:\n",
" current = queue.popleft()\n",
" print(current, end=\" \")\n",
"\n",
" for neighbor in graph[current]:\n",
" if neighbor not in visited:\n",
" visited.add(neighbor)\n",
" queue.append(neighbor)\n",
"\n",
"# 実行\n",
"start_node = 1\n",
"print(\"\\nBFS order:\")\n",
"bfs(G, start_node)"
]
},
{
"cell_type": "markdown",
"id": "1cadc7d0",
"metadata": {},
"source": [
"## NetworkX を使った DFS / BFS\n",
"NetworkX の関数を使用すると、より簡単に探索結果を取得できます。"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6c8ca0da",
"metadata": {},
"outputs": [],
"source": [
"# DFS (先行順) の探索順序を取得\n",
"dfs_result = list(nx.dfs_preorder_nodes(G, source=1))\n",
"print(\"NetworkX DFS preorder:\", dfs_result)\n",
"\n",
"# BFS の探索木を取得\n",
"bfs_tree = nx.bfs_tree(G, source=1)\n",
"print(\"NetworkX BFS tree edges:\", list(bfs_tree.edges()))"
]
}
],
"metadata": {},
"nbformat": 4,
"nbformat_minor": 5
}