Recent questions tagged breadth-first-search

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

Which of the following algorithms are based on the Breadth First Search (BFS) ?Prim's algorithmsKruskal algorithmsDijkstra algorithmsGreedy algorithmsDynamic ProgrammingC...

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

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

Let $G(V, E)$ be an undirected and unweighted graph with $100$ vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. ...

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

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

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

Consider the following undirected graph on $5$ nodes.Assume you are performing breadth-first search on this graph using a queue data structure. How many unique breadth fi...

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

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

Which of the following statements are true?Minimax search is breadth-first; it processes all the nodes at a level before moving to a node in next level.The effectiveness ...

What are the appropriate data structures for graph traversal using Breadth First Search(BFS) and Depth First Search(DFS) algorithms?Stack for BFS and Queue for DFSQueue f...

$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,\ v6v...

The diameter of a tree $T= (V, E)$ is defined as $max_{u,v\ \epsilon\ V}\ \delta(u,v)$, that is, the largest of all shortest-path distances in the tree. Give an efficient...

There are two types of professional wrestlers: “babyfaces” (“good guys”) and “heels” (“bad guys”). Between any pair of professional wrestlers, there may or may not be a r...

Give an example of a directed graph $G=(V, E)$, a source vertex $s\ \epsilon\ V$ , and a set of tree edges $E_{\Pi}\subseteq E$ such that for each vertex $v\ \epsilon\ V$...

What will be the path from A-H if BFS is used in the following graph?

Are the "n!" ways maximum possible BFS sequences ? ( Indirectly, for any given vertices is it obvious that complete graph will give max BFS sequences ? )