Test: Graph - 2 - Computer Science Engineering (CSE) MCQ

Option (A) is MNOPQR. It cannot be a BFS as the traversal starts with M, but O is visited before N and Q. In BFS all adjacent must be visited before adjacent of adjacent.
Option (B) is NQMPOR. It also cannot be BFS, because here, P is visited before O.
(C) and (D) match up to QMNP. We see that M was added to the queue before N and P (because M comes before NP in QMNP). Because R is M’s neighbor, it gets added to the queue before the neighbor of N and P (which is O). Thus, R is visited before O.

In DFS, if 'v' is visited
after 'u', then one of the following is true.
1) (u, v) is an edge.
     u
   /   \
  v     w
 /     / \
x     y   z

2) 'u' is a leaf node.
     w
   /   \
  x     v
 /     / \
u     y   z 
In DFS, after visiting a node, we first recur for all unvisited children. If there are no unvisited children (u is leaf), then control goes back to parent and parent then visits next unvisited children.

We can check all DFSs for following properties.

In DFS, if a vertex 'v' is visited
after 'u', then one of the following is true.
1) (u, v) is an edge.
     u
   /   \
  v     w
 /     / \
x     y   z

2) 'u' is a leaf node.
     w
   /   \
  x     v
 /     / \
u     y   z
In DFS, after visiting a node, we first recur for all unvisited children. If there are no unvisited children (u is leaf), then control goes back to parent and parent then visits next unvisited children.

In option D, 1 appears after 2 and 3 which is not possible in Topological Sorting.
In the given DAG it is directly visible that there is an outgoing edge from vertex 1 to vertex 2 and 3 hence 2 and 3 cannot come before vertex 1 so clearly option D is incorrect topological sort.
But for questions in which it is not directly visible we should know how to find topological sort of a DAG.

Depth First Search of a graph takes O(m+n) time when the graph is represented using adjacency list.

In adjacency matrix representation, graph is represented as an “n x n” matrix. To do DFS, for every vertex, we traverse the row corresponding to that vertex to find all adjacent vertices (In adjacency list representation we traverse only the adjacent vertices of the vertex). Therefore time complexity becomes O(n²)

The following diagram shows the worst case situation where the recursion tree has maximum depth.

So the recursion depth is 19 (including the first node).

Below example shows that A and B are FALSE:

Below example shows C is false:

Tree edges are the edges that are part of DFS tree.  If there are x tree edges in a tree, then  x+1 vertices in the tree.
The output of DFS is a forest if the graph is disconnected.  Let us see below simple example where graph is disconnected.

The above example matches with D option

More Examples:
1) All vertices  of Graph are connected.  k must be n-1.  We get number of connected components  = n- k =  n – (n-1) = 1
2) No vertex is connected. k must be 0.  We get number of connected components  = n- k =  n – 0 = n

Following are different 6 Topological Sortings
a-b-c-d-e-f
a-d-e-b-c-f
a-b-d-c-e-f
a-d-b-c-e-f
a-b-d-e-c-f
a-d-b-e-c-f

First you need to find twins of each node. You can do this using level order traversal (i.e., BFS) once. Time complexity of BFS is Θ(m +n).
And you have to use linked list for representation which is extra space (but memory size is not a constraint here).
Final, time complexity is Θ(m + n) to set twin pointer.

As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.
Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge.
All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V).

In case of BFS if we draw complete binary tree then in Set A we have level1+level2.
In DFS we have level1+ level 2 + level 3.

So A-B= remaining element of level 2.

Let Q(V) denote the quality-score of vertex V.

Q(S) = 1 (Given)
Q(C) = 1 (S → C)
Q(F) = 1 * 9 (S  → C  → F)
Q(A) = 9 (S  → A)
Q(D) = 9*1 (S  → A  → D)
Q(G) = 9 * 1 * 9 (S  → A  → D  → G)
Q(B) = 9 * 1 (S  → A  → B)
Q(E) = 9 * 1 * 9 (S  → A  → D  → E)
Q(T) = 9*1*9*9 (S  → A  → D  → E → T) 
Sum of quality-score of all vertices,

= 1 + 1 + 9 + 9 + 9 + 81 + 9 + 81 + 729 
= 929 

When vertices are arranged with difference of 8 there are 8 components as shown by 8 columns in the image below:

When vertices are arranged with difference of 12 the number of components is reduced to 4 as first column will be connected with fifth column, second column will be connected with sixth column, third column will be connected with seventh column and fourth column will be connected with eighth column. No other form of connection exists so total 4 connected components are there.

So, option (B) is correct.

In BST and balanced BST searching takes time in order of mlogn , where m is the maximum string length and n is the number of strings in tree . But searching in Trie will take O(m) time.
Hence , option C is the correct answer.

It’s a special case in which all edge weights are equal, so dfs would work and resultant depth first tree would be the spanning tree. So the answer would be O(m+n).

Both the hashing and the trie provides searching in the linear time. But trie requires extra space for storage and it is collision free. And trie allows finding all the strings with same prefix, so it is also called prefix tree.
Hence, option B is the correct option.

Trie is also known as Digital tree.
Hence , option D is the correct answer.

The worst case efficiency for a path compression algorithm is mathematically found to be O(M log N).
Hence, option A is correct.

By using Euler’s theorem, the number of regions = e – v + 2
R = e – v + 2
5 = e – 8 + 2 = e-6
e = 5+6 = 11