9.4 まとめ¶
1. 重要なポイントの振り返り¶
- グラフは頂点と辺から構成され、一組の頂点と一組の辺からなる集合として表せます。
- 線形関係（連結リスト）や分治関係（木）と比べて、ネットワーク関係（グラフ）は自由度が高く、そのぶん複雑です。
- 有向グラフの辺は方向性を持ち、連結グラフでは任意の頂点に到達でき、重み付きグラフの各辺は重み変数を含みます。
- 隣接行列は行列を用いてグラフを表し、各行（列）が 1 つの頂点を表し、行列要素が辺を表します。\(1\) または \(0\) を用いて、2 つの頂点の間に辺があるかないかを示します。隣接行列は追加・削除・検索・更新の操作効率が高い一方で、より多くの空間を消費します。
- 隣接リストは複数の連結リストを使ってグラフを表し、第 \(i\) 個の連結リストが頂点 \(i\) に対応し、その頂点に隣接するすべての頂点を格納します。隣接リストは隣接行列よりも省スペースですが、辺を探すために連結リストを走査する必要があるため、時間効率は低くなります。
- 隣接リスト内の連結リストが長くなりすぎた場合は、赤黒木やハッシュテーブルに変換することで、検索効率を高められます。
- アルゴリズムの考え方という観点では、隣接行列は「空間を時間と引き換えにする」ことを体現し、隣接リストは「時間を空間と引き換えにする」ことを体現します。
- グラフは、ソーシャルネットワークや地下鉄路線など、さまざまな現実のシステムをモデル化するために使えます。
- 木はグラフの特殊な一例であり、木の走査もグラフ走査の特殊な一例です。
- グラフの幅優先探索は、近いところから遠いところへ、層ごとに広がっていく探索方法であり、通常はキューを使って実装します。
- グラフの深さ優先探索は、まず行けるところまで進み、進めなくなったらバックトラックする探索方法であり、通常は再帰に基づいて実装します。
2. Q & A¶
Q：経路の定義は頂点列ですか、それとも辺列ですか？
Wikipedia では言語版ごとに定義が一致していません。英語版では「経路は辺の列」であり、中国語版では「経路は頂点の列」です。以下は英語版の原文です：In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices.
本書では、経路を頂点列ではなく辺列とみなします。これは、2 つの頂点の間に複数の辺が存在する可能性があり、その場合は各辺がそれぞれ 1 本の経路に対応するためです。
Q：非連結グラフには到達できない頂点がありますか？
非連結グラフでは、ある頂点から出発すると、少なくとも 1 つの頂点には到達できません。非連結グラフ全体を走査するには、グラフ内のすべての連結成分をたどれるように複数の始点を設定する必要があります。
Q：隣接リストにおいて、「その頂点に接続されたすべての頂点」の順序に決まりはありますか？
順序は任意でかまいません。ただし実際の応用では、頂点を追加した順序や頂点値の大小順など、特定の規則に従って並べ替える必要がある場合があります。そうすることで、「ある種の極値を持つ」頂点をすばやく見つけやすくなります。