CODEWITHSUNDEEP
breadth-first-search
RUstar
RUstar

Reputation: 37

How BFS can from a tree on certain directed graph?

It is said said BFS always gives a tree, while DFS gives a forest. But I do not understand how BFS can always give a tree. Consider this graph and starting point b

enter image description here

How do we get a tree here?

Upvotes: -1

Views: 641

Answers (4)

Chetan Naik
Chetan Naik

Reputation: 15

The OP refers to the statement made in CLRS with respect to the predecessor subgraph created by the BFS and DFS traversal.

The fact that BFS traversal always gives a BFS tree and not a forest (like in case of DFS) is due to the definition of the predecessor subgraph in case of BFS. It is defined for only one source vertex unlike DFS which is defined for all vertices.

Ref - enter image description here

Upvotes: 0

TJM
TJM

Reputation: 739

BFS not gives a tree. It use queue ,in fact. And alongside with DFS, BFS is also an algorithm to go through the tree.

Upvotes: 0

div
div

Reputation: 573

A tree is basically a connected graph(at least one path between every pair of nodes) with no cycles.

If we do BFS on a connected graph, we will visit every node in the graph and each node is visited only once. So, there is only one path from starting node to every node we visit, since we visit it only once. There is also only one path between any pair of nodes by same argument as above (it will make more sense if you imagine a graph and comprehend). So, there are no cycles and hence it's a tree.

Upvotes: 0

Gavin The Handsome
Gavin The Handsome

Reputation: 1

Don't understand why you have a directed graph and an terminal starting point b. From b, it can go nowhere but stay at b.

If it not directed, then it will be b->a->c->d, no matter it is BFS or DFS.

First time heard DFS returns a forest. Guess people think this because every time it reaches end it will return to parent node.

Upvotes: 0

Related Questions