0
$\begingroup$

Here I have a proof related to strongly connected graph from Algorithms book.

enter image description here

However, when I run DFS on the following 2 strongrly connected graph, I get different result than the proof.

enter image description here

According to property, highest post number in C is bigger than the highest post number in D but it is not. Where am I making mistake?

$\endgroup$

1 Answer 1

2
$\begingroup$

Your post-traversal numbering of the component $C$ is incorrect. The vertex labeled as $1,6$ was assigned its post-traversal number too early; a depth-first search will also explore the vertices of $D$ before assigning the post-traversal number to this vertex.

$\endgroup$
1
  • $\begingroup$ Thank you! I figured out too. $\endgroup$ Oct 2, 2019 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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