9.4 まとめ¶

1. 重要な復習¶

グラフは頂点と辺で構成されます。頂点の集合と辺の集合として記述できます。
線形関係（連結リストなど）や階層関係（木など）と比較して、ネットワーク関係（グラフ）はより大きな柔軟性を提供し、より複雑になります。
有向グラフでは、辺に方向があります。連結グラフでは、任意の頂点から他の任意の頂点に到達できます。重み付きグラフでは、各辺に関連する重み変数があります。
隣接行列は、行列（2次元配列）を使用してグラフを表現する方法です。行と列は頂点を表します。行列要素の値は、2つの頂点間に辺があるかどうかを示し、辺がある場合は\(1\)、ない場合は\(0\)を使用します。隣接行列は辺の追加、削除、チェックなどの操作に非常に効率的ですが、より多くのスペースが必要です。
隣接リストは、連結リストの集合を使用してグラフを表現するもう一つの一般的な方法です。グラフ内の各頂点には、その隣接するすべての頂点を含むリストがあります。\(i\)番目のリストは頂点\(i\)を表します。隣接リストは隣接行列と比較してより少ないスペースを使用します。ただし、辺を見つけるためにリストを走査する必要があるため、時間効率は低くなります。
隣接リストの連結リストが十分に長くなったとき、ルックアップ効率を向上させるために赤黒木やハッシュテーブルに変換できます。
アルゴリズム設計の観点から、隣接行列は「空間と時間のトレードオフ」の概念を反映し、隣接リストは「時間と空間のトレードオフ」を反映します。
グラフは、ソーシャルネットワークや地下鉄路線など、さまざまな現実世界のシステムをモデル化するために使用できます。
木はグラフの特別なケースであり、木の走査もグラフ走査の特別なケースです。
グラフの幅優先走査は、近くから遠くへと層ごとに拡張する探索方法で、通常キューを使用します。
グラフの深さ優先走査は、それ以上のパスがない場合にバックトラックする前に、まず終端に到達することを優先する探索方法です。しばしば再帰を使用して実装されます。

2. Q & A¶

Q: パスは頂点のシーケンスとして定義されますか、それとも辺のシーケンスとして定義されますか？

グラフ理論では、グラフ内のパスは頂点のシーケンスを結ぶ有限または無限の辺のシーケンスです。

この文書では、パスは頂点のシーケンスではなく、辺のシーケンスと考えられます。これは、2つの頂点を結ぶ複数の辺がある可能性があり、その場合各辺がパスに対応するためです。

Q: 非連結グラフでは、走査できない点がありますか？

非連結グラフでは、特定の点から到達できない頂点が少なくとも1つあります。非連結グラフを走査するには、グラフのすべての連結成分を走査するために複数の開始点を設定する必要があります。

Q: 隣接リストで、「その頂点に接続されたすべての頂点」の順序は重要ですか？

任意の順序で構いません。ただし、実際のアプリケーションでは、頂点が追加された順序や頂点値の順序など、特定のルールに従ってそれらをソートする必要がある場合があります。これにより、特定の極値を持つ頂点を素早く見つけることができます。