0 votes 0 votes 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 Programming in C graph-algorithms breadth-first-search + – Ayush Upadhyaya asked Nov 22, 2018 Ayush Upadhyaya 3.3k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Shaik Masthan commented Nov 22, 2018 reply Follow Share i didn't understood the algo given in the link, but as per me the classification which you did, is correct 0 votes 0 votes goxul commented Nov 22, 2018 reply Follow Share Watch this: https://www.youtube.com/watch?v=Ia6AgDENsf0 0 votes 0 votes srestha commented Nov 22, 2018 reply Follow Share @Shaik and @Ayush why BFS no need of forward edges? 0 votes 0 votes Shaik Masthan commented Nov 22, 2018 reply Follow Share mam, if it is a forward edge present , then it will recognize as tree edge at first step only ! 1 votes 1 votes Utkarsh Joshi commented Nov 22, 2018 reply Follow Share YES! your classification is correct! 0 votes 0 votes Deepanshu commented Nov 22, 2018 reply Follow Share 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 0 votes 0 votes Ayush Upadhyaya commented Nov 22, 2018 reply Follow Share 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. 1 votes 1 votes Shaik Masthan commented Nov 22, 2018 reply Follow Share 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 2 votes 2 votes Please log in or register to add a comment.