I've been working on this graph and just completely botching it. I mean to say that my solution may be the worst possible other than if a monkey had thrown darts at the graph to decide the next path. Anyhow, I'm lost and really trying to get a grasp of where my conclusion and the proper conclusion diverged dramatically.

I wanted to perform a DFS, show discovery/finish times, the DF forest, and edge classifications. I assumed that: 1) The vertices are listed in alphabetical order in each adjacency list. 2) The vertices are taken in the alphabetical order in the main loop of the DFS algorithm.

Should I be treating this as a directed acyclic graph?

  • $\begingroup$ It is hard to understand what you are asking here. You certainly have drawn directed graphs. $\endgroup$ Jun 17, 2013 at 23:58

1 Answer 1


$L$ has an edge to $K$, other than that, the DFS forest you've drawn is correct. And since $K$ would not be expanded before $L$, there should be an edge $LK$ in the BFS forest.

  • $\begingroup$ New users can't upvote so maybe someone else can help you out. But yes I understand your solution and where I was going wrong. Thanks. $\endgroup$
    – stackuser
    Jun 18, 2013 at 1:28

Your Answer

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

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