グラフアルゴリズム入門:初心者でも理解しやすい解説記事

基本情報技術者
この記事は約9分で読めます。
記事内に広告が含まれています。
広告

グラフアルゴリズム入門

グラフアルゴリズムは、グラフ構造(ノードとエッジで構成されるデータ構造)を解析・操作するためのアルゴリズムです。この記事では、グラフアルゴリズムの基本概念と一般的なアルゴリズムを学びます。

目次

  1. グラフとは
  2. グラフの表現方法
  3. 深さ優先探索 (DFS)
  4. 幅優先探索 (BFS)
  5. 最短経路問題
  6. 最小全域木問題

ステップ1: グラフとは

グラフはノード(頂)とエッジ(辺)で構成されるデータ構造です。ノードはデータを表し、エッジはノード間の関係性を表します。

ステップ2: グラフの表現方法

グラフは主に2つの方法で表現されます。

  1. 隣接リスト(Adjacency List)
  2. 隣接行列(Adjacency Matrix)

隣接リスト

隣接リストは、各ノードが保持するエッジのリストです。Pythonでは、辞書やリストのリストで表現できます。

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

隣接行列

隣接行列は、ノード数×ノード数の二次元配列で表現されます。エッジが存在する場合は1、存在しない場合は0を格納します。

graph = [
    [0, 1, 1, 0, 0, 0],
    [1, 0, 0, 1, 1, 0],
    [1, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 1],
    [0, 0, 1, 0, 1, 0],
]

ステップ3: 深さ優先探索 (DFS)

深さ優先探索(DFS)は、グラフ探索のアルゴリズムの1つです。現在のノードから深く探索し、行き止まりに達したら戻って別のパスを探索します。

DFSの実装

def dfs(graph, node, visited):
    if node not in visited:
        visited.add(node)
        print(node, end=" ")
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

visited = set()
dfs(graph, "A", visited)

ステップ4: 幅優先探索 (BFS)

幅優先探索(BFS)は、グラフ探索のアルゴリズムの1つです。現在のノードから同じ深さのノードを探索し、次の深さに進んで探索を続けます。

BFSの実装

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)

bfs(graph, "A")

ステップ5: 最短経路問題

最短経路問題は、与えられたグラフで2つのノード間の最短経路を見つける問題です。重み付きグラフでは、最短経路の重みの合計が最も低いものを見つけます。一般的なアルゴリズムにはダイクストラ法とベルマンフォード法があります。

ダイクストラ法

ダイクストラ法は、負の重みがないグラフで最短経路を見つけるアルゴリズムです。

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1},
}

print(dijkstra(graph, 'A'))

ベルマンフォード法

ベルマンフォード法は、負の重みがあるグラフでも最短経路を見つけることができるアルゴリズムです。

def bellman_ford(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight

    return distances

print(bellman_ford(graph, 'A'))

ステップ6: 最小全域木問題

最小全域木問題は、与えられたグラフの全てのノードを含む最小の重み付き部分グラフを見つける問題です。一般的なアルゴリズムにはプリム法とクラスカル法があります。

プリム法

プリム法は、最小全域木を構築するためのアルゴリズムです。

import heapq
import random

def prim(graph):
    visited = set()
    edges = [(0, random.choice(list(graph.keys())))]
    total_weight = 0

    while edges:
        weight, node = heapq.heappop(edges)

        if node not in visited:
            visited.add(node)
            total_weight += weight
            for neighbor, edge_weight in graph[node].items():
                if neighbor not in visited:
                    heapq.heappush(edges, (edge_weight, neighbor))

    return total_weight

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1},
}

print(prim(graph))

クラスカル法

クラスカル法は、最小全域木を構築するための別のアルゴリズムです。

def find(parent, node):
    if parent[node] == node:
        return node
    return find(parent, parent[node])

def union(parent, rank, node1, node2):
    root1 = find(parent, node1)
    root2 = find(parent, node2)

    if rank[root1] > rank[root2]:
        parent[root2] = root1
    elif rank[root1] < rank[root2]:
        parent[root1] = root2
    else:
        parent[root2] = root1
        rank[root1] += 1

def kruskal(graph):
    edges = []
    for node in graph:
        for neighbor, weight in graph[node].items():
            edges.append((weight, node, neighbor))
    edges.sort()

    parent = {node: node for node in graph}
    rank = {node: 0 for node in graph}
    total_weight = 0

    for edge in edges:
        weight, node1, node2 = edge
        if find(parent, node1) != find(parent, node2):
            union(parent, rank, node1, node2)
            total_weight += weight

    return total_weight

print(kruskal(graph)) 

これらのアルゴリズムは、グラフ理論とアルゴリズムの基本的な概念をカバーしています。他にも多くの高度なグラフアルゴリズムが存在しますが、これらの基本を理解することで、より複雑な問題に取り組む準備ができるでしょう。

 

タイトルとURLをコピーしました