グラフ（導入）

本セクションでは二分木で扱った内容を前提とします。まずはグラフとは何かについて改めて確認しましょう。

グラフとは以下の図のような「 対象とそれらの間でのつながりを表すデータ構造」 です。グラフにおける「対象」は一般的にnode(ノード)またはvertex(頂点)と呼ばれ、図では丸で表されています。「つながり」はノード同士の関係を表し、edge(エッジ)または辺と呼ばれます。図ではノード間を結んでいる線で表しています。InterviewCatでは基本的にノードとエッジで呼称していきます。

グラフは向きと重さによって大まかに以下の4つに分類されます。この概念は二分木のセクションでは扱わなかったですが、非常に重要なのでしっかり理解しましょう。

	重みなし	重みあり
無向	重みなし無向グラフ	重みあり無向グラフ
有向	重みなし有向グラフ	重みあり有向グラフ