How to classify an edge that is not traversed in a depth-first search?

Question

I have an assignment that requires one to perform a depth-first search on a directed graph and to classify all edges of the graph. However, I'm confused as to how one would classify an edge that is not traversed during the course of the depth-first search, seeing as how these edges are classified during the course of a search.

Let me summarize a depth-first search on the above pictured graph.

First we go from 1 to 2. Then we pop 2 off the stack, because there is nowhere to go, so we're back at 1. Then we go from 1 to 3. Next we go from 3 to 4.

Ok, so assuming I got that part right, then all the edges traversed are Tree edges correct? So, how would one classify the edges between 3 to 2 and the edge from 4 to 3?

Answer 1

Your DFS should still traverse the edges from 3->2 and 4->3. They would be a cross edge and a back edge, respectively, IIRC.

You'll only actually push a node onto the stack the first time you see it, but when you do visit it, you look at all of its outgoing edges, whether their destinations have already been visited or not.