基本情報技術者試験の科目BをJavaとPythonのプログラムで考える　No.3

基本情報技術者試験で出題されるプログラム言語が疑似言語に変更されましたね。合格に向けて学習を進めるにおいては、やはり普段から使っているプログラム言語に置き換えて考えてみたいですよね。
このサイトでは、IPA情報処理推進機構で公開されている科目Bのプログラミングの問題を中心に、疑似言語をJavaとPythonのコードに置き換えて解説していきます。
１日１問の解説を発信していく予定です。基本情報技術者試験の合格を目指されている方のお役に立てれば幸いです。

---

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

https://www.ipa.go.jp/shiken/mondai-kaiotu/sg_fe/koukai/eid2eo0000007g1d-att/2024r06_fe_kamoku_b_qs.pdf

問３　グラフ理論

この問題はグラフ理論が題材とされていますので、まずは基本事項を整理しておきます。

・グラフ理論とは
　　数学および計算機科学の分野の一つで、グラフと呼ばれる構造を研究する理論。グラフは、頂点（ノード）と、それらの頂点を結ぶ辺（エッジ）で構成される。

・無向グラフとは
　　頂点（ノード）とそれらを結ぶ辺（エッジ）で構成される。各辺には方向がない。AとBという2つの頂点があり、これらを結ぶ辺が存在するとき、無向グラフでは「AからBへ」という方向と「BからAへ」という方向は区別されない。

・隣接行列とは
　　グラフを表現する方法の一つで、グラフの頂点間の接続関係を行列として表したもの。グラフの頂点数を𝑛 としたとき、 n×n の正方行列として表される。

・正方行列とは
　　行数と列数が同じ行列

・行列の対角成分とは
　　行番号と列番号が同じ位置にある要素

・対称行列とは
　　行と列を入れ替えても変わらない行列

１．Javaのコードで考えてみよう

package kamokuB;

public class R6_Sample03 {
	
	//引数 edgeList で辺の配列を，引数 nodeNum でグラフの頂点の個数を受け取り
	//隣接行列を表す整数型の二次元配列を返す。
	static int[][] edgesToMatrix(int[][] edgeList,int nodeNum){
	    int[][] adjMatrix = new int[nodeNum][nodeNum];
	    int i, u, v;

	    for (i = 1; i < edgeList.length; i++){
	        u = edgeList[i][0];
	        v = edgeList[i][1];
	        adjMatrix[u][v] = 1;
	        adjMatrix[v][u] = 1;
	    }
	    return adjMatrix;
	}
	
	public static void main(String[] args) {
		int[][] edge = {{0,0},{1, 3}, {1, 4}, {3,4}, {2, 4}, {4, 5}};
		int[][] matrix = edgesToMatrix(edge,edge.length);
		
		for(int i = 1; i < matrix.length; i++) {
			for(int j = 1; j < matrix[i].length; j++)
				System.out.print(matrix[i][j] + " ");
		    System.out.println();
		}
	}	
}

２．Pythonのコードで考えてみよう

# R6サンプル問題3

def edges_to_matrix(edge_list, node_num):
    adj_matrix = [[0] * node_num for _ in range(node_num)]
    
    for i in range(1, len(edge_list)):
        u = edge_list[i][0]
        v = edge_list[i][1]
        adj_matrix[u][v] = 1
        adj_matrix[v][u] = 1
    
    return adj_matrix


edge = [[0, 0], [1, 3], [1, 4], [3, 4], [2, 4], [4, 5]]
matrix = edges_to_matrix(edge, len(edge))
    
for i in range(1, len(matrix)):
    for j in range(1, len(matrix[i])):
        print(matrix[i][j], end=" ")
    print()

いかがでしょうか。
グラフ理論とかが出てくると、初めて目にする人は戸惑いますよね。でも、問題文をじっくりと読むと、意外とすんなり理解できたりします。
あきらめたら終わりですよ。