グラフの表現方法（隣接リスト、隣接行列）の詳細解説

2024年8月17日2024年9月2日

概要:

今日のトピックは、グラフの代表的な表現方法である隣接リストと隣接行列についてです。これらの表現方法は、グラフアルゴリズムの効率性に大きく影響を与えるため、データ構造を理解する上で非常に重要です。

基本概念の説明:

隣接リスト

隣接リスト: グラフの各頂点に対して、その頂点から直接接続されている隣接頂点をリストとして持つデータ構造です。この表現は、疎なグラフ（エッジが少ないグラフ）に対して効率的であり、メモリ使用量が少なくなります。

隣接行列

隣接行列: グラフを頂点数×頂点数の行列として表現します。行列の要素が1であれば対応する頂点間にエッジが存在し、0であれば存在しないことを示します。この方法は、密なグラフ（エッジが多いグラフ）に適しており、エッジの存在確認が高速に行えますが、メモリを多く消費します。

各言語でのサンプルコード:

Python:

# 隣接リストによるグラフ表現
class GraphAdjList:
    def __init__(self, vertices):
        self.graph = [[] for _ in range(vertices)]

    def add_edge(self, src, dest):
        self.graph[src].append(dest)

# 隣接行列によるグラフ表現
class GraphAdjMatrix:
    def __init__(self, vertices):
        self.graph = [[0] * vertices for _ in range(vertices)]

    def add_edge(self, src, dest):
        self.graph[src][dest] = 1

C#:

using System;
using System.Collections.Generic;

class GraphAdjList
{
    private List[] graph;

    public GraphAdjList(int vertices)
    {
        graph = new List[vertices];
        for (int i = 0; i < vertices; i++)
            graph[i] = new List();
    }

    public void AddEdge(int src, int dest)
    {
        graph[src].Add(dest);
    }
}

class GraphAdjMatrix
{
    private int[,] graph;

    public GraphAdjMatrix(int vertices)
    {
        graph = new int[vertices, vertices];
    }

    public void AddEdge(int src, int dest)
    {
        graph[src, dest] = 1;
    }
}

C++:

#include <iostream>
#include <vector>

class GraphAdjList {
    std::vector<std::vector<int>> graph;
public:
    GraphAdjList(int vertices) : graph(vertices) {}

    void addEdge(int src, int dest) {
        graph[src].push_back(dest);
    }
};

class GraphAdjMatrix {
    std::vector<std::vector<int>> graph;
public:
    GraphAdjMatrix(int vertices) : graph(vertices, std::vector<int>(vertices, 0)) {}

    void addEdge(int src, int dest) {
        graph[src][dest] = 1;
    }
};

Java:

import java.util.*;

class GraphAdjList {
    private List<List<Integer>> graph;

    public GraphAdjList(int vertices) {
        graph = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++)
            graph.add(new ArrayList<>());
    }

    public void addEdge(int src, int dest) {
        graph.get(src).add(dest);
    }
}

class GraphAdjMatrix {
    private int[][] graph;

    public GraphAdjMatrix(int vertices) {
        graph = new int[vertices][vertices];
    }

    public void addEdge(int src, int dest) {
        graph[src][dest] = 1;
    }
}

JavaScript:

class GraphAdjList {
    constructor(vertices) {
        this.graph = Array.from({ length: vertices }, () => []);
    }

    addEdge(src, dest) {
        this.graph[src].push(dest);
    }
}

class GraphAdjMatrix {
    constructor(vertices) {
        this.graph = Array.from({ length: vertices }, () => Array(vertices).fill(0));
    }

    addEdge(src, dest) {
        this.graph[src][dest] = 1;
    }
}

各言語の解説:

言語	特徴	メリット	デメリット
Python	柔軟なデータ構造操作が可能	簡潔なコード	実行速度が遅い
C#	.NETエコシステムとの統合	型安全性が高い	プラットフォーム依存
C++	高速でメモリ効率が良い	詳細なメモリ管理が可能	コードが複雑
Java	プラットフォームに依存しない	大規模なプロジェクトに最適	メモリ消費が多い
JavaScript	Webベースのアプリケーションに最適	非同期処理が簡単	言語特有の癖がある

まとめ:

隣接リストと隣接行列は、グラフの表現方法として広く使われています。どちらを選ぶかは、グラフの密度やメモリ効率、アクセス速度の要件に依存します。次は、これらの表現方法を用いた具体的なグラフアルゴリズムの実装について学習しましょう。

よかったらシェアしてね！

URLをコピーしました！

URLをコピーしました！

コメント一覧（1件）

プログラミング学習ガイド | カテゴリ別目次 より:

2024年9月11日 10:44 AM

[…] 1-2-1. グラフの表現方法（隣接リスト、隣接行列） […]

返信