Data Structures and Algorithms MCQ - Graph Algorithm

16 Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth first traversal, which of the following statement is correct?

d(r, v) and d(r, v) will be equal when u and v are at same level, otherwise d (r, v) will be less than d(r, v)

17 The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

Applying BFS Algorithms
Starting from Q
Queue Q
Making Q’s child’s status 1.
Queue
Q| M| N| P
Making M’s child 1 (which are not 1)

Status
Q	M	N	O	P	R
2	1	1		1
2	2	1		1	1
2	2	2	1	1	1

Q| M| N| P| R
Making N’s Child 1
Q| M| N| P| R| O
(other are already 1)

18 Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is

Maximum possible value of n for which we have complete tree and our 't' node is the last leaf node at height 4.
So, the maximum possible value of n
= 1 + 2 + 4 + 8 + 16
= 31

19 Let G = (V, E) be an undirected graph with a subgraph G₁ = (V₁, E₁). Weights are assigned to edges of G as follows:

A single-source shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex v₁ of V₁ as the source. Which of the following can always be inferred from the path costs computed?

Suppose G = (v, E) and G₁ = (v, E₁) such that E₁ ≤ E and v₁ ≤ v
Consider an example

Consider the w(e) = 1 of e ∉ E1 it means the cost of v₁ to v₄ is only 1 other edges having cost 0. It is noted that G₁ is connected (As shown in example).

20 Let G = (V, E) be a direction graph with n vertices. A path from vi to v in G is sequence of vertices (vi, 1, ..., such that (vk, vki)E E for all k in i through j — 1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follow:

Consider the following algorithm for i = 1 to n for j = 1 to n for k = 1 to n A [j, k] = max (AU, k], (A[j, i] + A[i, k])); Which of the following statements is necessarily true for all j and k after terminal of the above algorithm?

for i = 1 ton
for j = 1 ton
for K = 1 ton
A[j, K] = max (j, K], A[j, i) + a(i, K)]
Anxn Matrix and A[j, K] = 1 if (j, K) ∈ E
so there exist a path from J to K and must contain A[j, K] edges