in DS recategorized by
10,826 views
6 votes
6 votes
Consider the following statements:
1. Let T be the DFS tree resulting from DFS traversal on a connected directed graph the root of the tree is an articulation point, iff it has at least two children.
2. When BFS is carried out on a directed graph G, the edges of G will be classified as tree edge, back edge, or cross edge and not forward edge as in the case of DFS.

Find TRUE or FALSE for both the statements
in DS recategorized by
10.8k views

4 Comments

1
1
yes :p
0
0

1st qs came in gate 2021 😶

0
0

1 Answer

5 votes
5 votes
1) An articulation point is a node which when deleted splits the graph into more than one component. This can be found out by performing DFS on the graph. The root of the DFS tree can only be an articulation point iff it has more than one child. Hence this is TRUE.
2) For case of a BFS on a directed graph there can only be tree, back or cross edges and distinguishing between cross and back edges cannot be done based on the order of traversal alone, contrary to the case of a DFS. This is also TRUE.

4 Comments

@suparna kar 

it is working now..

1
1

Watch this video it will clear all your doubts of types of edges

1
1
Wow right @ tym i needed.

Thanks!
0
0

Related questions