隣接行列(adjacency matrix)について簡単に解説しています。
隣接行列はグラフを表現するための方法の1つです。頂点(ノード)と頂点の関係を表現するために使用されるものです。
例えば上記の三角形にAとBとCという頂点(ノード)があった場合に、これをテーブルで表してみます。
テーブルで表すと上記のようになります。次に三角形にAとBとCという頂点(ノード)がありますが、2つの頂点が接続されていない場合は、テーブル上に0を書き込みます。2つの頂点が接続されていない場合は線(エッジ)がない、または隣接していないともいえます。
次に2つの頂点が接続されている場合はテーブルに1を書き込みます。2つの頂点が接続されている場合は、線(エッジ)で接続されている、または隣接しているともいえます。
そしてテーブル上に書き込みをしたものが上記となります。これは頂点(ノード)と頂点の関係を表現していますので、隣接行列となります。
なお、今回の場合では、
・AとA
・BとB
・CとC
この3つは線(エッジ)で接続されていない、または隣接していないので「0」と書き込みます。これがややこしいです。
コメント