ある要素を関連付けて整理したり、分析したりするために、要素間のつながりをグラフとして分析する手法のこと。
いろいろな要素を点に置き換え、その関連性を辺で結び特徴を分析する。
グラフ(G)は、有限個の点(V)と辺(E)から構成されます。点はグラフを構成する各頂点で、辺は頂点同士を結びます。ひとつの点についている辺の数を次数という。一般に、グラフはG=(V,E)と定義します。
辺に向きがないものを無向グラフ(上図左)、向きがあるものを有向グラフ(上図右)と言います。
有向グラフの場合、点に入ってくる辺の数を入次数といい、点から出ていく辺の数を出次数という。
この図の場合、e1=(v1,v2),e2=(v2,v3),e3=(v1,v3)と表記します。一般に、e=(vi,vj)のvi,vjをそれぞれ端点と言います。
隣接行列はグラフを表現するために用いる行列である。
行は自分の点を表し、列は相手の点を表す。
点と点に辺がつながっている場合は1、つながっていない場合は0とする。
スタート地点から距離の近い地点から順に最短経路を確定させ、その地点に隣接する地点の最短経路を必要に応じて更新していくことで、スタート地点から各地点への最短経路を求めていきます。
www.it-shikaku.jp