グラフ理論の基礎——ネットワーク・知識グラフの土台

SNSの「友達の友達」、GoogleマップのルートB探索、ChatGPTが参照する知識グラフ——これらはすべてグラフ理論という共通の数学的基盤の上に成り立っている。グラフ理論はAI・機械学習の文脈でも、知識表現・推薦システム・グラフニューラルネットワーク（GNN）の形で存在感を増している。本記事ではグラフ理論の基本を、コードを交えながら体系的に解説する。

グラフとは何か

グラフ（Graph）はノード（頂点）とエッジ（辺）の集合で構成されるデータ構造だ。

ノード: {A, B, C, D}
エッジ: {(A,B), (B,C), (C,D), (A,D)}

    A --- B
    |     |
    D --- C

グラフはネットワーク状の関係を表現するのに優れている。

問題	ノード	エッジ
SNS	ユーザー	フォロー関係
地図	交差点	道路
知識グラフ	概念・エンティティ	関係（is-a, has-a など）
依存グラフ	パッケージ	依存関係

グラフの種類

無向グラフと有向グラフ

無向グラフ（Undirected Graph）: エッジに向きがない。A-B というエッジは A→B と B→A の両方を意味する。友達関係（相互）が典型例。

有向グラフ（Directed Graph / Digraph）: エッジに向きがある。フォロー関係（一方向も可能）、Web ページのリンク構造が典型例。

# Python での実装（辞書を使った隣接リスト）

# 無向グラフ
undirected = {
    'A': ['B', 'D'],
    'B': ['A', 'C'],
    'C': ['B', 'D'],
    'D': ['A', 'C']
}

# 有向グラフ（Aは Bを指すが、BはAを指さない）
directed = {
    'A': ['B', 'D'],
    'B': ['C'],
    'C': ['D'],
    'D': []
}

重み付きグラフ

エッジに数値（重み）が付いたグラフ。距離・コスト・類似度などを表現できる。

# 重み付き有向グラフ（隣接リスト + 重み）
weighted = {
    'A': [('B', 4), ('D', 2)],
    'B': [('C', 3), ('D', 1)],
    'C': [('D', 5)],
    'D': []
}

特殊なグラフ

木（Tree）: 閉路のない連結グラフ。ファイルシステム・組織図
DAG（有向非巡回グラフ）: 閉路のない有向グラフ。タスク依存関係・コンパイル順序
二部グラフ（Bipartite Graph）: ノードを2つのグループに分け、グループ内にエッジがない。推薦システム（ユーザー×アイテム）

グラフの表現方法

隣接行列

n×n の行列で、matrix[i][j] = 1 はノード i から j へのエッジが存在することを意味する。

import numpy as np

# 4ノードの無向グラフ
# ノード順: [A, B, C, D]
adj_matrix = np.array([
    [0, 1, 0, 1],  # A
    [1, 0, 1, 0],  # B
    [0, 1, 0, 1],  # C
    [1, 0, 1, 0],  # D
])

# エッジ (A,B) の確認
print(adj_matrix[0][1])  # 1 (存在する)
print(adj_matrix[0][2])  # 0 (存在しない)

長所: エッジの有無を O(1) で確認できる短所: n² のメモリが必要。疎なグラフ（エッジが少ない）では非効率

隣接リスト

各ノードの隣接ノードをリストで管理する。

# 辞書を使った隣接リスト
graph = {
    0: [1, 3],  # A
    1: [0, 2],  # B
    2: [1, 3],  # C
    3: [0, 2],  # D
}

# エッジ (A,B) の確認
print(1 in graph[0])  # True

# 全エッジを列挙
for node, neighbors in graph.items():
    for neighbor in neighbors:
        if node < neighbor:  # 重複を避ける
            print(f"({node}, {neighbor})")

長所: 疎なグラフでメモリ効率が良い（実際のグラフのほとんどは疎）短所: エッジの有無確認が O(次数) になる場合がある

BFS——幅優先探索

BFS（Breadth-First Search、幅優先探索）は、スタート地点から近い順にノードを探索するアルゴリズムだ。キュー（FIFO）を使って実装する。

from collections import deque

def bfs(graph, start):
    """幅優先探索"""
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1],
    5: [2]
}

print(bfs(graph, 0))  # [0, 1, 2, 3, 4, 5]

BFS の用途

最短経路探索（重みなしグラフ）: BFS は必ず最短経路を見つける
ソーシャルネットワークの「N 度の繋がり」: 1度→2度→… の順に探索
Web クローリング: BFS でページをたどる

def shortest_path(graph, start, end):
    """BFS による最短経路（重みなし）"""
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        node, path = queue.popleft()
        if node == end:
            return path

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # 経路なし

print(shortest_path(graph, 0, 5))  # [0, 2, 5]

DFS——深さ優先探索

DFS（Depth-First Search、深さ優先探索）は、一方向に進めるだけ進み、行き止まりになったら戻るアルゴリズムだ。スタック（再帰またはリスト）を使う。

def dfs_recursive(graph, node, visited=None):
    """深さ優先探索（再帰版）"""
    if visited is None:
        visited = set()

    visited.add(node)
    print(node, end=' ')

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

    return visited


def dfs_iterative(graph, start):
    """深さ優先探索（反復版）"""
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            order.append(node)
            # スタックに積む順序で探索順が変わる
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

    return order

graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1],
    5: [2]
}

print(dfs_iterative(graph, 0))  # [0, 1, 3, 4, 2, 5]

DFS の用途

迷路の解法: 壁を伝って探索
サイクル検出: 既に訪問済みのノードに辿り着いたらサイクルあり
トポロジカルソート: DAG のノードを依存関係順に並べる

def topological_sort(graph):
    """DAG のトポロジカルソート（DFS ベース）"""
    visited = set()
    result = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        result.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)

    return result[::-1]

# タスク依存関係: A→B→D, A→C→D
dag = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

print(topological_sort(dag))  # ['A', 'C', 'B', 'D'] or ['A', 'B', 'C', 'D']

BFS vs DFS の使い分け

観点	BFS	DFS
データ構造	キュー（FIFO）	スタック（LIFO）/ 再帰
探索順	近い順に広がる	深く潜ってから戻る
最短経路（重みなし）	保証される	保証されない
メモリ使用	幅が広いと多くなる	深さに比例
用途	最短経路・SNS距離	サイクル検出・トポソート・迷路

知識グラフとAI

知識グラフ（Knowledge Graph）は、エンティティ（ノード）と関係（エッジ）で世界の知識を表現するグラフ構造だ。

(東京, 首都, 日本)
(日本, 隣接国, 韓国)
(ChatGPT, 開発元, OpenAI)
(OpenAI, 投資元, Microsoft)

LLM と知識グラフを組み合わせた RAG（Retrieval-Augmented Generation）では、グラフ探索で関連情報を取得し、LLM に渡すことでハルシネーションを抑制できる。

# 簡単な知識グラフの実装例
class KnowledgeGraph:
    def __init__(self):
        self.triples = []  # (subject, predicate, object) のリスト
        self.index = {}    # subject → [(predicate, object)] のインデックス

    def add(self, subject, predicate, obj):
        triple = (subject, predicate, obj)
        self.triples.append(triple)
        if subject not in self.index:
            self.index[subject] = []
        self.index[subject].append((predicate, obj))

    def query(self, subject, predicate=None):
        results = self.index.get(subject, [])
        if predicate:
            return [obj for pred, obj in results if pred == predicate]
        return results

kg = KnowledgeGraph()
kg.add("東京", "首都", "日本")
kg.add("日本", "隣接国", "韓国")
kg.add("ChatGPT", "開発元", "OpenAI")

print(kg.query("ChatGPT", "開発元"))  # ['OpenAI']
print(kg.query("日本"))  # [('隣接国', '韓国')]

グラフニューラルネットワーク（GNN）の直感

GNN はグラフ構造データに対してニューラルネットワークを適用する手法だ。各ノードは隣接ノードの情報を集約（aggregate）し、自身の表現を更新する。

初期状態: 各ノードに特徴ベクトルを割り当て
第1ステップ: 各ノードが隣接ノードの特徴を集約
第2ステップ: 集約した情報で自身の特徴を更新
...繰り返し...
最終的な各ノードの埋め込みを予測に使用

レコメンドシステム（ユーザー×アイテムの二部グラフ）、分子設計（原子＝ノード、結合＝エッジ）、ソーシャルネットワーク分析などで活用されている。

ライブラリを使った実践

Python では networkx が定番のグラフライブラリだ。

import networkx as nx
import matplotlib.pyplot as plt

# グラフ作成
G = nx.Graph()
G.add_edges_from([('A','B'), ('B','C'), ('C','D'), ('D','A'), ('A','C')])

# 基本的な分析
print("ノード数:", G.number_of_nodes())
print("エッジ数:", G.number_of_edges())
print("次数:", dict(G.degree()))

# 最短経路
path = nx.shortest_path(G, 'A', 'D')
print("最短経路:", path)

# 中心性（どのノードが重要か）
centrality = nx.betweenness_centrality(G)
print("媒介中心性:", centrality)

# 可視化
nx.draw(G, with_labels=True, node_color='lightblue', node_size=500)
plt.show()

まとめ

グラフ理論はシンプルな概念——ノードとエッジ——から出発して、現代のAI・データ工学の中核をなす強力な道具を提供する。

グラフの基本: ノード・エッジ・有向/無向・重み付き
表現方法: 隣接行列（小規模・密なグラフ）vs 隣接リスト（大規模・疎なグラフ）
BFS: 幅優先で近い順に探索、重みなし最短経路に最適
DFS: 深さ優先で探索、サイクル検出・トポロジカルソートに最適
知識グラフ: エンティティ×関係の表現、RAGと組み合わせLLMを強化
GNN: グラフ構造データへのニューラルネットワーク適用

グラフ的思考——物事をノードと関係の網として捉える視点——は、複雑なシステムを設計・分析するうえで強力な認知ツールになる。

#グラフ理論 #アルゴリズム #知識グラフ #BFS #DFS

免責事項 — 掲載情報は執筆時点のものです。料金・機能は変更される場合があります。最新情報は各公式サイトをご確認ください。