IPA FE Subject B 2024 Question 3
A question IPA Japan published in 令和６年度 基本情報技術者試験 科目B 公開問題 問3, translated into English. ITPEC is based on the same exams.
From the answer group below, select the correct answer to be inserted into blank in the program. Here, the array index starts at 1.
The vertices of the graph shown in Figure 1 are numbered with integers in order, starting from 1. The graph is an undirected graph, and there is at most one edge between any two vertices. One edge can be represented by an integer-type array with two elements, whose elements are the numbers of the vertices at both ends. For example, {1, 3} represents the edge whose end points are vertex 1 and vertex 3. The whole graph can be represented by an array that stores all the two-element arrays representing the edges contained in the graph (hereinafter referred to as the array of edges). The number of elements in the array of edges is equal to the number of edges in the graph. The graph in Figure 1 can be represented as the array of integer-type arrays {{1, 3}, {1, 4}, {3, 4}, {2, 4}, {4, 5}}.
Figure 1 Example of a graph
The function edgesToMatrix converts an array of edges into an adjacency matrix. An adjacency matrix is a square matrix whose numbers of rows and columns are equal to the number of vertices contained in the graph, and its element in row i, column j is 1 when there is an edge connecting vertex i and vertex j, and 0 otherwise. The diagonal elements of the matrix are all 0, and in the case of an undirected graph, it is a symmetric matrix. Figure 2 shows the adjacency matrix that represents the graph in Figure 1.
Figure 2 Adjacency matrix that represents the graph in Figure 1
The function edgesToMatrix receives the array of edges as the argument edgeList and the number of vertices of the graph as the argument nodeNum, and returns an integer-type two-dimensional array that represents the adjacency matrix.
Answer group
Explanation
adjMatrix[u, v] ← 1 and adjMatrix[v, u] ← 1 — each edge of an undirected graph must mark both cells of the adjacency matrix, row u column v and row v column u.
An edge {u, v} joins vertex u and vertex v, and the matrix of an undirected graph is symmetric. Each edge appears only once in edgeList ({1, 3}, never also {3, 1}), so the loop body must set both adjMatrix[ and adjMatrix[.
Running the loop for the five edges of Figure 1 with both assignments:
Row 4 becomes 1 1 1 0 1 and row 3 becomes 1 0 0 1 0, exactly the matrix of Figure 2; the diagonal stays 0.
Answer (d)
Why not others:
- •(a), (b) and (f) — set only diagonal cells such as
adjMatrix[, a vertex joined to itself; Figure 2's diagonal is all 0, and the edges' cells stay 0u, u] - •(c) — sets only row
u, columnv: the result is the upper half of Figure 2 only, so row 4 comes out0 0 0 0 1instead of1 1 1 0 1and the matrix is not symmetric - •(e) — sets only row
v, columnu: the lower half only, so row 1 comes out all 0 instead of0 0 1 1 0
Key rule: An undirected edge is stored once in an edge list but twice in an adjacency matrix, at [u, v] and at [v, u], which is why the matrix is symmetric.
Graph Traversal · AI-written, may contain errors
This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.