グラフの隣接行列への変換【基本情報技術者試験 科目B 公開問題】

← 科目Bの公開問題一覧へ戻る

　基本情報技術者試験の科目Bの公開問題を題材に，グラフを隣接行列に変換する方法について学習します。この問題では，無向グラフの辺を隣接行列に反映する処理と，二次元配列の値の変化を確認します。

令和6年度 基本情報技術者試験 公開問題 科目B 問3

問　次のプログラム中の 　　　　　 に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。

　図1に示すグラフの頂点には，1から順に整数で番号が付けられている。グラフは無向グラフであり，各頂点間には高々一つの辺がある。一つの辺は両端の頂点の番号を要素にもつ要素数2の整数型の配列で表現できる。例えば，{1，3} は頂点1と頂点3を端点とする辺を表す。グラフ全体は，グラフに含まれる辺を表す要素数2の配列を全て格納した配列（以下，辺の配列という）で表現できる。辺の配列の要素数はグラフの辺の個数と等しい。図1のグラフは整数型配列の配列 {{1，3}，{1，4}，{3，4}，{2，4}，{4，5}} と表現できる。

　関数 edgesToMatrix は，辺の配列を隣接行列に変換する。隣接行列とは，グラフに含まれる頂点の個数と等しい行数及び列数の正方行列で，i行j列の成分は頂点iと頂点jを結ぶ辺があるときに1となり，それ以外は0となる。行列の対角成分は全て0で，無向グラフの場合は対称行列になる。図1のグラフを表現する隣接行列を図2に示す。

　関数 edgesToMatrix は，引数 edgeList で辺の配列を，引数 nodeNum でグラフの頂点の個数をそれぞれ受け取り，隣接行列を表す整数型の二次元配列を返す。

〔プログラム〕

○整数型の二次元配列: edgesToMatrix(整数型配列の配列: edgeList，

　　　　　　　　　　　　　　　　　　 整数型: nodeNum)

　整数型の二次元配列: adjMatrix ← {nodeNum行nodeNum列の 0}

　整数型: i，u，v

　for (i を 1 から edgeListの要素数 まで 1ずつ増やす)

　　u ← edgeList[i][1]

　　v ← edgeList[i][2]

　　　　　　　

　endfor

　return adjMatrix

解答群

ア　adjMatrix[u，u] ← 1

イ　adjMatrix[u，u] ← 1

　　adjMatrix[v，v] ← 1

ウ　adjMatrix[u，v] ← 1

エ　adjMatrix[u，v] ← 1

　　adjMatrix[v，u] ← 1

オ　adjMatrix[v，u] ← 1

カ　adjMatrix[v，v] ← 1

【参考】	「極限値・グラフ理論・待ち行列理論の基礎まとめ（グラフ理論とは）」

この問題のポイント

　この問題から学べることは，

• グラフの辺を配列で表現する方法
• グラフを隣接行列で表現する方法
• 無向グラフでは，辺の両端に対応する2か所を1にする処理
• 二重の添字をもつ二次元配列の値を更新する方法

です。特に，無向グラフでは頂点uと頂点vを結ぶ辺があるとき，adjMatrix[u，v] と adjMatrix[v，u] の両方を1にすることを理解しておきましょう。

基本情報技術者試験の学習におすすめの参考書

基本情報技術者試験の合格を目指す方におすすめの参考書です。