# Graph Traversal (BFS and DFS)

 Question 1
Let $U = \{1, 2, 3\}$. Let $2^U$ denote the powerset of $U$. Consider an undirected graph $G$ whose vertex set is $2^U$. For any $A,B \in 2^U, (A,B)$ is an edge in $G$ if and only if (i) $A \neq B$, and (ii) either $A \subseteq B$ or $B \subseteq A$. For any vertex $A$ in $G$, the set of all possible orderings in which the vertices of $G$ can be visited in a Breadth First Search (BFS) starting from $A$ is denoted by $B(A)$.
If $\phi$ denotes the empty set, then the cardinality of $B(\phi )$ is ____.
 A 524 B 63218 C 5040 D 2540
GATE CSE 2023   Algorithm
Question 1 Explanation:
 Question 2
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.
Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.
Which of the following options is/are correct?
 A Root of T can never be an articulation point in G. B Root of T is an articulation point in G if and only if it has 2 or more children. C A leaf of T can be an articulation point in G. D If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.
GATE CSE 2021 SET-1   Algorithm
Question 2 Explanation:

 Question 3
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?
 A v2v4 B v1v4 C v4v5 D v3v4
ISRO CSE 2020   Algorithm
Question 3 Explanation:
 Question 4
Which of the following is application of Breath First Search on the graph?
 A Finding diameter of the graph B Finding bipartite graph C Both (A) and (B) D None of the above
ISRO CSE 2018   Algorithm
Question 4 Explanation:
 Question 5
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.

(I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j|=1.

Which of the statements above must necessarily be true?
 A I only B II only C Both I and II D Neither I nor II
GATE CSE 2018   Algorithm
Question 5 Explanation:

There are 5 questions to complete.