Recent questions tagged graph-search

Consider the following algorithm someAlgo that takes an undirected graph $G$ as input. ...

Let $\text{G = (V, E)}$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in \text{V},$ let $d(x)$ denote the shortest distanc...

​​​​Let $G$ be a directed graph and $T$ a depth first search $\text{(DFS)}$ spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth first searc...

The number of edges present in the forest generated by the $\text{DFS}$ traversal of an undirected graph $G$ with $100$ vertices is $40$. The number of connected componen...

Consider the following statements:$\text{P}$: There exists no simple, undirected and connected graph with $80$ vertices and $77$ edges.$\text{Q}$: All vertices of Euler g...

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$...

Which of the following statement is true?For a directed graph, the absence of back edges in a DFS tree can have cycle.If all edge in a graph have distinct weight then the...

How can we distinguish b/w back edge, the forward edge and cross edge in BFS or DFS traversal in Graphs?

Please explain why first option is wrong Question: 12Choose the true statement.1.Preorder traversal of tree resembles the depth first search of the graph.2.Inorder traver...

Consider the following graph:What is maximum depth of recursive calls for processing graph by using DFS?5678

I want to know in which condition we should apply BFS and DFS for GRAPH Search ? And why?

Which of the following statements are false ?$1.$ A depth-first search of a directed graph always produces the same number of tree edges (i.e., independent of the order i...