Recent questions tagged depth-first-search

Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason RAssertion A: Depth first search can be used to perform a topological s...

Which of the following statements about DFS are correct?It can detect cycles in a graphIt can be used to find connected components.It works for both directed and undirect...

Consider a directed graph $G=(V, E)$, where $V$ is the finite set of vertices and $E$ is the set of directed edges between the vertices. $G$ may contain cycles but there ...

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time a...

Suppose the input directed graph $G(V,E)$ is a DAG. For an edge $(u,v)\in E$, which of the following will NEVER be correct in DFS discovery/finish times?$d[u] < d[v] < f[...

Consider a directed graph $G=(V, E)$, where $V=\{0,1,2, \ldots, 100\}$ and $E=\{(i, j): 0<j-i \leq 2$, for all $i, j \in V\}$. Suppose the adjacency list of each vertex i...

​​​​Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph $G$ is/are TRUE?A DFS tree of $G$ is...

​​​​​Consider a state space where the start state is number $1$. The successor function for the state numbered $n$ returns two states numbered $n+1$ and $n+2$. Assume tha...

Consider performing Depth-First Search (DFS) on an undirected and unweighted graph $\bar{G}$ starting at vertex $S$. For any vertex $u$ in $G$, where $d[u]$ is the length...

BFS DFS question asking the number of nodes expanded BFS = DFSBFS $$ DFSNone

Let $\text{b}$ be the branching factor of a search tree. If the optimal goal is reached after $\text{d}$ actions from the initial state, in the worst case, how many times...

Which of the following statements is/are true?A. In a labelled undirected connected simple graph G, all the depth-first search from same node form same tree.B. In a label...

Consider the following graph : For the graph; the following sequences of depth first search (DFS) are given$\text{abcghf}$$\text{abfchg}$$\text{abfhgc}$$\text{afghbc}$Whi...

Please list the problems where BFS alone can do and DFS alone can do and both can do??