The Gateway to Computer Science Excellence
0 votes
293 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 by Boss (27.8k points) | 293 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?
0
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.
+1
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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,542 answers
195,692 comments
101,529 users