SUNY Geneseo Department of Computer Science

Depth First Search

Return to List of Lectures

Questions?

Depth First Search

Try it by hand

Can you use DFS to find cycles in a graph? How? How sure are you that it always works?

• Run a DFS modified to return “true” (there is a cycle) as soon as it sees a back edge, and to return “false” (no cycle) if it finishes the search without seeing any back edge
• Back edge implies cycle: path of tree edges from head of back edge to tail, back edge closes cycle
• Cycle implies back edge: from white-path theorem

Mazes

• You can represent a maze as a graph whose vertices are junctions, dead ends, entrance, and exit (i.e., points in the maze where there are decisions about what to do), and whose edges represent the existence of a decision-free path between two decision points
• DFS is interesting here because people can do it in a maze, as long as they have some way to keep track of the recursion

Hand out DFS problem set

Next

Divide and conquer algorithms

Read

• Section 2.3.1 (the merge procedure isn’t important now though)
• Section 4.1 up to but not including “Analyzing the divide-and-conquer algorithm” (top of page 68 through first half of 73)