3
$\begingroup$

Introduction to Algorithms books claims BFS only classifies an edge for an undirected graph to be either tree or cross edge. But how about this simple example below where forward edges are naturally appearing?

Given graph with just 2 vertices A and B and 3 edges from A to B!

exploring A adjacent vertices

(1) A->B (tree edge, A is now marked as an ancestor for B and B is A's descendant)

(2) A->B (forward edge? B is not yet processed (gray) and we found an edge to it from its ancestor(A))

(3) A->B forward edge using the same reasoning as in (2)!

What am I missing here?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

My example was a multigraph (multiple edges between a given pair of vertices is allowed). And in multigraph BFS does "produce" forward edges!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.