ITPEC FE Graph Traversal Questions with Answers

Graph Traversal

2 questions · Fundamental Engineering

Oct 2025 · Question 9

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(1), 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.

Constructor	Description
`Queue()`	Creates an empty queue.

Method	Return value	Description
`enqueue(integer: elm)`	None	Adds the integer `elm` as an element to the queue.
`dequeue()`	`integer`	Extracts the element from the queue and returns it.
`isEmpty()`	`boolean`	Returns `true` if the queue is empty; otherwise, returns `false`.

Figure 2 Explanation of the class Queue

[Program]

global: integer [,]: graph ← {{0, 1, 0, 1, 0},

{1, 0, 1, 0, 1},

{0, 1, 0, 0, 0},

{1, 0, 0, 0, 1},

{0, 1, 0, 1, 0}}

○ traverse(integer: k)

Queue: queue ← Queue()

boolean []: visited ← {false, false, false, false, false}

integer: v, i

queue.enqueue(k)

visited[k] ← true

while (not queue.isEmpty())

v ← queue.dequeue()

output v

for (increase i from 1 to 5 by 1)

if (graph[v,i] = 1 and visited[i] = false)

queue.enqueue(i)

visited[i] ← true

endif

endfor

endwhile

Answer group

a)“1”, “2”, “3”, “4”, “5”b)“1”, “2”, “3”, “5”, “4”c)“1”, “2”, “4”, “3”, “5”d)“1”, “2”, “4”, “5”, “3”e)“1”, “2”, “5”, “4”, “3”f)“1”, “4”, “5”, “2”, “3”

Oct 2024 · Question 9

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(1), the output is in the order blank.

Figure Structure of the graph

[Program]

global: integer: n ← 5

global: integer [][]: graph ← {{0, 1, 0, 1, 0}, {1, 0, 1, 0, 1},

{0, 1, 0, 0, 0}, {1, 0, 0, 0, 1},

{0, 1, 0, 1, 0}}

global: boolean []: visited ← {false, false, false, false, false}

○ traverse(integer: k)

integer: i

visited[k] ← true

output k

for (increase i from 1 to n by 1)

if (graph[k][i] = 1 and visited[i] = false)

traverse(i)

endif

endfor

Answer group

a)1, 2, 3, 4, 5b)1, 2, 3, 5, 4c)1, 2, 4, 3, 5d)1, 2, 4, 5, 3