読者です 読者をやめる 読者になる 読者になる

ALDS_11_A Graphを解く話

グラフの表現の理解を問う問題である.

隣接リスト表現から隣接行列表現へ変換する処理を実装する.

隣接リスト表現(Adjacency List)

・有限グラフを表現するためのリスト
・1つのリストが1つの頂点に対応して,隣接するノードが接続

隣接行列表現(Adjacency Matrix)

・有限グラフを表現するための行列
・行列の各要素は頂点のペアが隣接しているか否かを示す.

以下のサイトで,グラフと辺をいじったり行列とリストを確認できる.

https://visualgo.net/graphds

 

実装

入力は
 頂点番号u 出次数k uに隣接する頂点v_1, v_2, ..., v_k
の形式で与えられる.

u = 1\ to\ nを行番号, j = 1\ to\ kを列番号にする.
頂点のペアに対して1は辺あり,0は辺なしで隣接行列 m_{uj}に代入.

gist6e33ed8e2c8bdb6f8de899f271efe4f7

 

感想

シンプルなのでかなり簡単な問題.