BFS

An undirected, unweighted, simple graph $G(V, E)$ is said to be 2 -colorable if there exists a function $c: V \rightarrow\{0,1\}$ such that for every $(u, v) \in E, c(u) \neq c(v)$...

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

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 the maximum value...

Consider the following algorithm someAlgo that takes an undirected graph G as input. someAlgo (G) 1. Let v be any vertex in G. Run BFS on G starting at v. Let u be a vertex in G at...

Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. W...

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

Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let B denote the se...

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph belo...

Breadth First Search $$(BFS)$$ is started on a binary tree beginning from the root vertex. There is a vertex $$t$$ at a distance four from the root. If t is the $$n$$-th vertex in...

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For $$x \in V$$, let d(x) denote the shortest distance in G from s to x. A breadt...

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

Level order traversal of a rooted tree can be done by starting from the root and performing

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

Which one of the following statements is false?