グラフは、ノード（頂点） とそれらをつなぐ エッジ（辺） から構成されるデータ構造です。リンクリストや木（ツリー）は、 階層構造や特定の子ノード数といった性質を持つ、グラフの特別な形態です。グラフは、交通ネットワークやソーシャルネットワーク、 化学構造など、あらゆる関係性を柔軟に表現できるため、非常に重要な意味を持っています。本記事では、グラフの基本概念とその表現方法について解説します。

グラフの種類

グラフにはさまざまな種類があり、それらを理解することはグラフを表現し、アルゴリズムを構築する上で重要です。 グラフが 有向グラフ であるのは、エッジに向きがある場合であり、エッジに向きがない場合は 無向グラフ です。 例えば、すべてのエッジが互いに指し合うポインタのペアで表現されている場合、グラフは無向と見なされます。 有向グラフが 閉路（サイクル） を含む場合、それは サイクリックグラフ（循環グラフ） と呼ばれます（例: ノード同士が互いに指し合う場合、自身を指す場合、または3つ以上のノードでループを形成する場合）。 一方、閉路を含まない場合は 非循環グラフ（アサイクリックグラフ） と呼ばれます。

グラフ内のエッジに距離や時間、期待値などの値が割り当てられている場合、それは 重み付きグラフ と呼ばれます。 一方、エッジに値がない場合は 重みなしグラフ と呼ばれます。エッジがまったく存在しないグラフは 空グラフ（ヌルグラフ） です。 また、すべてのノードが他のすべてのノードと接続されている場合、それは 完全グラフ と呼ばれます。 ノードに比べてエッジが相対的に少ないグラフは 疎グラフ（スパースグラフ）、エッジが多いグラフは 密グラフ（デンスグラフ） と呼ばれます。 これらの説明をもとに、上記のグラフの種類を特定してみてください（これはクイズのQ1です）。

隣接行列（Adjacency Matrix）

グラフはさまざまな方法で表現できますが、その1つが 隣接行列（Adjacency Matrix） を使用する方法です。 この方法では、行列内の各値が、行に対応するノードから列に対応するノードへのエッジを表します。 重み付きグラフの場合、値に重みを含めることができ、重みなしグラフの場合はエッジの有無を示す2値（0または1）を使用します。 エッジをクエリする操作は、matrix[i][j] を参照するだけで済むため、時間計算量は $O(1)$ です。

class AdjacencyMatrix {
    public:
        vector<vector<int> > mat;
 
        void addEdge(int i, int j) {
            if (i < mat.size() && j < mat.size())
            {
                mat[i][j] = 1;
                mat[j][i] = 1;
            }
            else
            {
                cout << "Error: Invalid vertex index." << endl;
            }
        };
 
        void display() {
            for (const auto &row : mat)
            {
                for (int val : row)
                {
                    cout << val << " ";
                }
                cout << endl;
            }
        };
 
    AdjacencyMatrix(int size) {
        mat.resize(size, vector<int>(size, 0));
    };
};

しかし、隣接行列は、特に疎な無向グラフの場合、行列はスパース（疎行列）かつ対称になるため、必要以上に多くのメモリを消費してしまいます。 実際、隣接行列の空間計算量は $O(V^2)$ であり、ここで $V$ はノード数を表します。

隣接リスト（Adjacency List）

グラフを表現する別の方法として隣接リストがあります。これはノードとその接続された頂点を対応付けるリンクリストの配列です。存在する頂点のみを格納するため、隣接リストの空間計算量は $O(V + E)$ であり、ここで $E$ は辺の数を表します。グラフが完全グラフでない限り、隣接リストは隣接行列よりも常にメモリ効率が高いです。ただし、ノード $i$ からノード $j$ へのエッジが存在するかどうかを確認する場合、配列の $i$ 番目のインデックスにアクセスしてリンクリストをたどり $j$ を探す必要があるため、時間計算量は $O(E)$ になります。

class AdjacencyList {
    public:
        vector<list<int> > li;
 
        void addEdge(int i, int j) {
            li[i].push_back(j);
            li[j].push_back(i);
        };
 
        void display() {
            for (int i = 0; i < li.size(); i++) {
                cout << i << ": ";
                for (int j : li[i]) {
                    cout << j << " ";
                }
                cout << endl; 
            }
        };
 
    AdjacencyList(int size) {
        li.resize(size);
    };
};

新しいノードの追加は隣接リストの方が隣接行列よりも高速です。隣接行列では $(V+1)^2$サイズの新しい行列を作成する必要があるため計算量は $O(V^2)$ ですが、隣接リストの場合は配列に新しい要素を追加するだけで済み、計算量は $O(1)$ です。そのため、メモリに余裕があり、 ノード数が比較的固定されていて、エッジのクエリが頻繁に行われる場合は隣接行列が推奨されます。一方で、メモリが限られていて、グラフ構造が頻繁に変化する場合は隣接リストの方が適しています。

結論

この記事では、グラフの種類とその表現方法について説明しました。グラフ理論は強化学習やグラフ機械学習の分野と密接に関連しているため、 新しい記事シリーズでさらに詳しく掘り下げるかもしれません。次回の記事では、グラフをどのように探索して検索を実行するかを取り上げます。

クイズ

この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。

リソース

• GeeksforGeeks. 2024. Graph and its representations. GeeksforGeeks.