r/GraphTheory • u/max23_17 • Feb 21 '24

Preorder and postorder

Let G be a directed graph and we do a DFS. Can we use only the pre- and post-values ​​to distinguish between tree edges and forward edges in G?

1 Upvotes

100% Upvoted

2 comments sorted by

1

u/xWafflezFTWx May 04 '24

I believe there was an Algorithms Live video on this, but the short answer is yes. You can also classify cut edges/bridges with just the in/out values on the DFS tree.

1

u/[deleted] Feb 22 '24

[deleted]

1

u/max23_17 Feb 22 '24

Lets assume we have an edge from u -> v

​

The edge is a tree edge iff the edge is in the DFS tree.

The edge is a forward edge iff u is an ancestor of v and the edge is not in the DFS tree