※本情報は解説作成時点のもので、閲覧時点では法改正等により情報が変更になっている場合がございます。あらかじめご理解いただければ幸いです。
正解は「D.adjMatrix[u, v] ← 1
adjMatrix[v, u] ← 1」です。
無向グラフの隣接行列では、頂点uとvを結ぶ辺がある場合、(u,v)と(v,u)の両方を1に設定します。
この記事では、基本情報技術者試験（FE）試験（令和6年度）科目Bで出題された第3問「辺の配列から隣接行列への変換」について、試験対策の観点からわかりやすく解説します。
Contents
隣接行列とは
頂点iと頂点jが結ばれていれば adjMatrix[i,j]＝1
隣接行列は、頂点数×頂点数の正方行列で表されます。
辺が存在する場合に1、存在しない場合に0を格納します。
対角成分（i＝j）は常に0です。
無向グラフのポイント
- 無向グラフは辺に向きがない
- (u,v)があれば、同時に(v,u)も成立する
- 隣接行列は対称行列になる
そのため、1本の辺を処理するたびに、2か所に1を代入する必要があります。
なぜ2か所に代入するのか
- u ← edgeList[i][1]
- v ← edgeList[i][2]
- uとvは両端の頂点番号
よって、adjMatrix[u, v] と adjMatrix[v, u] の両方を1にすることで、無向グラフの性質を正しく表現できます。
他の選択肢が誤りである理由
- adjMatrix[u,u] ← 1：対角成分は常に0
- adjMatrix[v,v] ← 1：自己ループを意味してしまう
- 片側のみ代入：対称性が保たれない
無向グラフである点を見落とすと誤答になります。
問われているポイント
この問題では、グラフ表現（辺の配列と隣接行列）の対応関係と、無向グラフの性質が理解できているかが問われています。
データ構造の基礎として重要なテーマです。
気を付けてほしい点（勘違いしやすいポイント）
- 無向グラフ＝必ず対称行列
- 対角成分は0（自己ループなし）
補足
グラフの表現方法（隣接行列・隣接リスト）は基本情報技術者試験（FE）試験の頻出分野です。特徴を整理しておきましょう。
基本情報技術者試験（FE）試験での出題パターン
基本情報技術者試験（FE）試験では、グラフの表現変換や探索アルゴリズムが頻出です。
無向か有向かの違いは特に重要なポイントです。
この知識が使われている問題
まとめ
- 無向グラフの隣接行列は対称行列
- 1本の辺につき2か所に1を代入する