search
Log In
0 votes
728 views

In BFS of a directed graph, we don't have forward edges.Only tree edge,cross edge or back edge.

Below is a sample graph I have taken and classified edge types.

Please verify guys whether it's correct.

The algorithm I have used is the pseudocode given by "redtuna" in the selected answer here.

https://stackoverflow.com/questions/29631211/edge-classification-during-breadth-first-search-on-a-directed-graph

in Programming 728 views
0
i didn't understood the algo given in the link, but as per me the classification which you did, is correct
0

Watch this: 

0
@Shaik  and @Ayush

why BFS no need of forward edges?
1
mam, if it is a forward edge present , then it will recognize as tree edge at first step only !
0
YES! your classification is correct!
0

Shaik Masthan plzz ellaborate ur line

mam, if it is a forward edge present , then it will recognize as tree edge at first step only 

1
Recognition of forward edge requires say for a Edge A->B, B should have been visited before the edge A-B is discovered and this can happen only when B is visited via some other vertex using more than one edge.Since, BFS finds shortest path from source in terms of smaller number of edges, When Vertex A is enqueued, edge A-B will be discovered and marked a tree or cross edge.Hence forward edges never possible.
2
What is forward edge? Let there is a tree edge between A to B and B to C then A --> C is a forward edge, think  that At A itself C is pushed into queue then there is no chance of A --> C is look as forward edge

Please log in or register to answer this question.

Related questions

6 votes
1 answer
1
3.3k views
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 ... 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
asked Jan 27, 2018 in DS MIRIYALA JEEVAN KUMA 3.3k views
0 votes
0 answers
2
72 views
HOW CAN WE GET A CROSS EDGE WHILE PERFORMING A BFS ON UNDIRECTED AND DIRECTED GRAPH CAN ANYONE SHOW WITH AN EXAMPLE?
asked Nov 21, 2018 in Programming codingo1234 72 views
2 votes
0 answers
3
193 views
what is the question asking exactly?
asked Jan 11, 2018 in Programming gari 193 views
1 vote
1 answer
4
139 views
What will be the path from A-H if BFS is used in the following graph?
asked Feb 2, 2019 in Algorithms saptarshiDey 139 views
...