本セクションでは二分木で扱った内容を前提とします。まずはグラフとは何かについて改めて確認しましょう。
グラフとは以下の図のような「対象とそれらの間でのつながりを表すデータ構造」です。グラフにおける「対象」は一般的にnode(ノード)またはvertex(頂点)と呼ばれ、図では丸で表されています。「つながり」はノード同士の関係を表し、edge(エッジ)または辺と呼ばれます。図ではノード間を結んでいる線で表しています。InterviewCatでは基本的にノードとエッジで呼称していきます。
グラフは向きと重さによって大まかに以下の4つに分類されます。この概念は二分木のセクションでは扱わなかったですが、非常に重要なのでしっかり理解しましょう。
ㅤ | 重みなし | 重みあり |
無向 | 重みなし無向グラフ | 重みあり無向グラフ |
有向 | 重みなし有向グラフ | 重みあり有向グラフ |
