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

2023
Views:

165

Pages:

25
Author:

Pieroobc1

First Step: POP A NODE OFF THE STACK! Example Stack: A B C D A E Pop a node off the stack. A F Second Step: PUSH THE NEW NEIGHBORS ONTO THE STACK! Example Stack: A B C E D F What are the new neighbors of A? Example Stack: A B C E D F Push the new neighbors of root A onto the stack. A D C B Example Stack: A B C E Pop a node off the stack. AD D F D C B Example Stack: A B C E D F Push the new neighbors of D onto the stack. AD F C B Example Stack: A B C E Pop a node off the stack. ADF D F F C B Example Stack: A B C E D F C B C is already visited! Push the new neighbors of F onto the stack. ADF Example Stack: A B C E Pop a node off the stack. ADFC D F C B Example Stack: A B C E D F Push the new neighbors of C onto the stack. ADFC E B Example Stack: A B C E Pop a node off the stack. ADFCE D F E B Example Stack: A B C D B E F There are none! Push the new neighbors of E onto the stack. ADFCE Example Stack: A B C D B E Pop a node off the stack. ADFCEB F Example Stack: A B C E D F There are none! Push the new neighbors of B onto the stack. ADFCEB Example Stack: A B C E D F The next step would be to pop a node off the stack. ADFCEB But since the stack is empty, we’re done! Example A B Did you find it strange that although we pushed in the neighbors from left to right (e.g. B, C, D), the order of the search that we got back starts on the right? C E D F ADFCEB That’s because we used a stack! Last in first out, remember? If we want to search to end up A B C E F D, all we have to do is to push the neighbors into the stack from right to left (e.g. D, C, B). DFS and Maze Traversal The DFS algorithm is similar to a classic strategy for exploring a maze. We go as far as possible on one path until we reach a dead end. Then, we retrace our steps and go somewhere we haven’t visited before until we reach a dead end. Now you try it! Stack 1 Stack Stack Stack Pop off ____. Pop off ____. Pop off ____. Stack Stack Stack Pop off ____. Pop off ____. Pop off ____. Now you try it! Stack From previous slide! Stack Stack Stack Pop off ____. Pop off ____. Pop off ____. Stack Stack Stack Pop off ____. Pop off ____. Pop off ____. Now you try it! Stack 1 Stack Pop off __1_. 2 7 8 Stack 5 6 7 Pop off __4_. 8 Stack 3 6 7 Pop off __2_. 8 Stack Stack Pop off __5_. 4 Stack 5 6 7 Pop off __3_. 8 6 7 8 Pop off __6_. 7 8 Now you try it! Stack 7 8 From previous slide! Stack Stack Pop off __7_. 8 Stack 11 Pop off _10_. 12 9 Pop off __8_. 12 Stack Pop off _11_. 12 Stack 10 11 Pop off __9_. 12 Stack Pop off _12_. BFS vs. DFS L0 L1 A B L2 A C E BFS ABCDEF D F B C E D F DFS ADFCEB Applications BFS    Finding the shortest path Testing for bipartiteness Bipartite graphs are useful for modeling matching problems DFS  Maze Problem Bipartite Graphs

Graphics Traversal Chapter 4

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock