University:
Boston University
Course:
CAS MA 555 | Numerical Analysis I
Academic year:

2020
Views:

213

Pages:

10
Author:

Kameron Atkinson

Depth-First Search A B C E D F Depth-First Search Depth-first search (DFS) is a another technique for traversing a graph. A DFS traversal of a graph returns the nodes of the graph by traveling deep through one path until hitting a dead end and then retracing the steps. What is a DFS traversal? Let’s start at A A B C E D F What is a DFS traversal? 1 2 3 4 6 5 What is a DFS traversal? Let’s start at A A B C E ABCEFD D F Is that the only DFS? What is a DFS traversal? 1 6 4 5 2 3 Computer Algorithm Let’s look at how a computer would perform DFS! Stack A stack is a pile. If you put books in a pile, the last book will be on the top, and it will be the first one to be retrieved. Last In, First Out Example Stack: A B C D A E F Let’s start at A! Push the root A onto the stack. Our Algorithm is the SAME! Except, this time, we’re using a stack! Each time, we’re going pop a node (we’ll call it node X) off the stack. Then, we’re going to push all of the new neighbors of node X onto the stack.