グラフの種類

グラフの種類には大きく分けて４つあります。

名前	特徴
無向グラフ	エッジに方向がない
有向グラフ	エッジに方向がある
重みつき無向グラフ	エッジに重みがあり、方向がない
重みつき有向グラフ	エッジに重みがあり、方向がある

無向グラフの例

友達関係をグラフにした例です。この例ではエッジに方向をもたせていません。例えば、「友達の友達は友達としたとき、Ａ君とＢ君は友達ですか？」や「いくつの友達グループがありますか？」などの問題が考えられます。



有向グラフの例

物事の手順をグラフにした例です。朝起きてから学校に行くまでの簡単な手順を示していますが、このグラフから様々な要素が読み取れます。例えば、朝起きてから朝食を食べなくても学校へ行けますが、着替えなければ学校には行けないことが分かります。起きて→着替えて→学校へ行く、というのがこの手順の最短経路となります。



重みつき無向グラフの例

各ノードが市町を表し、エッジが市町を行き来するのにかかる時間を表しています（架空のもの）。ある町からある町への最短経路を求めたいなどの類の問題はよくあります。




ここで取り上げたものは、ほんの例でしかありません。「すべての問題はグラフで表せる」と言われるほど、グラフ構造は様々な問題で応用されます。