GATE CS Graph Traversals (BFS, DFS) questions

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:

Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below. Which of the following is not a topological ordering?

Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$. which one of the following statements is true?

Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that have one vertex in $X$ and one vertex in $Y$. Let the weight of an edge $e$ denote the …

Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that have one vertex in $X$ and one vertex in $Y$. The edge $e$ must definitely belong to:

Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1}) \in 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 \times n$ array initialized as follows: …

Consider the following graph: Among the following sequences: abeghf abfehg abfhge afghbe Which are the depth-first traversals of the above graph?

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 statements is correct?

Let $G$ be an undirected graph. Consider a depth-first traversal of $G$, and let $T$ be the resulting depth-first search tree. Let $u$ be a vertex in $G$ and let $v$ be the first new (unvisited) vertex visited after visiting $u$ in the traversal. Which of the following statement is always true?

The most appropriate matching for the following pairs $$\begin{array}{|l|l|}\hline \text{X: depth first search} & \text{1: heap } \\ \hline \text{Y: breadth first search} & \text{2: queue} \\ \hline \text{Z: sorting} & \text{3: stack} \\ \hline \end{array}$$ is:

Which of the following statements is false?