# How to perform alphabetically ordered DFS?

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?

• It is hard to understand what you are asking here. You certainly have drawn directed graphs. – András Salamon Jun 17 '13 at 23:58

## 1 Answer

$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.

• 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. – stackuser Jun 18 '13 at 1:28