415 views
1 votes
1 votes
Which of the following statements is false ?

a)Optimal binary search tree construction can be performed efficiently using dynamic programming

b)BFS can not be used to find connected components of a graph

c) Given the prefix and postfix walks of a bianry tree , the tree can not be re-constructed uniquely

d)DFS can be used to  find connected components of a graph

1 Answer

Best answer
1 votes
1 votes

option "B" false

BFS use to find no of connected components

It is straightforward to compute the connected components of a graph in linear time (in terms of the numbers of the vertices and edges of the graph) using either breadth-first search or depth-first search. In either case, a search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning. To find all the connected components of a graph, loop through its vertices, starting a new breadth first or depth first search whenever the loop reaches a vertex that has not already been included in a previously found connected component.

selected by

Related questions

1 votes
1 votes
0 answers
1
Sanjay Sharma asked Jan 23, 2017
180 views
0 votes
0 votes
2 answers
3
Sanjay Sharma asked Jan 22, 2017
639 views
The maximum size of the data that the application layer can pass on to the TCP layer below is ____________a)216 bytes b)216 +TCP header lengthc) 216 + TCP header lengthd...
0 votes
0 votes
1 answer
4
Sanjay Sharma asked Jan 22, 2017
625 views
ECL is the fastest of all logic families . High speed in ECL is possible because transistors are used in distance amplifier configuration , in which they are never drive...