recategorized by
13,185 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
recategorized by

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.

Related questions

0 votes
0 votes
1 answer
2
syncronizing asked Aug 23, 2018
2,519 views
Which does this sentence mean?In BFS of an undirected graph, there are no back edge and no forward edge.
0 votes
0 votes
1 answer
3