Graph Traversal
4 questions · Fundamental Engineering
From the answer group below, select the correct answer to be inserted into blank in the description. Here, the array index starts at 1.
The procedure traverse traces through a vertex of the graph in Figure 1, and outputs all vertex numbers in the graph. One of the vertex numbers of the graph is specified with the argument k. The global 2-dimensional array graph represents the graph in Figure 1. Each element graph[i,j] is equal to 1 if there is an edge between vertices i and j, and 0 otherwise. The array visited stores boolean values, where visited[i] indicates whether vertex i of the graph has been visited or not during the procedure. When the procedure is called as traverse(, the output is in the order blank.
Figure 1 Graph that is handled by the program
Here, the procedure traverse uses a queue represented by the class Queue. Figure 2 provides an explanation of the class Queue.
Figure 2 Explanation of the class Queue
Answer group
From the answer group below, select the correct answer to be inserted into blank in the description. Here, the array indexes start at 1.
The procedure traverse traces through a vertex of the graph shown in the Figure, and outputs all vertex numbers in the graph. The vertex number of the graph is specified with the argument k. The global variable n indicates the number of vertices in the graph. The global array graph represents the graph in the figure. Each element graph[i][j] is equal to 1 if an edge exists between vertices i and j, and it is equal to 0 otherwise. The global array visited stores boolean values, where visited[i] indicates whether vertex i of the graph has been visited during the procedure.
When the procedure is called as traverse(, the output is in the order blank.
Figure Structure of the graph
Answer group
From the answer group below, select the correct combination of answers to be inserted into A and B in the description.
In tic-tac-toe, the move with which you have the highest possibility of winning is determined. With the following procedure, the state transitions of the game are represented as a tree structure, and the evaluation value of each node other than the root is calculated. As a result, the move with the highest evaluation value among the children of the root is regarded as the move with the highest possibility of winning. A move selected by you is represented by ○, and a move selected by the opponent is represented by ×.
When the game is in the state of the root at the top of the figure, there are three moves you can select. Of them, the evaluation value of the child pointed to by A is A, and the evaluation value of the child pointed to by B is B.
Figure State transitions of tic-tac-toe
Answer group
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