Description

Discussion 10 DFS, BFS, SPs, MSTs Announcements Welcome back from spring break! Hope you had a restful week :) Reach out to your mentor GSI if you feel yourself falling behind, or are feeling overwhelmed -- we’re here for you! We want to help you finish as strong as you can. We will be running the full autograder for project 2AB on ~4/2 Midterm 2 this Friday, April 5th from 8-10pm! ○ Check out @3764 for important information about the midterm & review sessions! No lab due this week! We’ll be doing exam review in lab. 61B Imposter Syndrome Panel ○ Sunday, 4/7 from 5-6:30pm in Soda 310 Remember to complete the anonymous spring break survey for 8 points of EC! Discussion survey: tinyurl.com/cz-disc10-sp19 Agenda Focus on what has the highest votes, but we’ll try to get through everything! Graph Traversals Level-Order/Breadth First Search (BFS): ○ Visit top to bottom, left to right, just like how you read! Depth-order/Depth First Search (DFS): ○ Traverse “deeper” nodes before shallow ones Preorder vs. Postorder vs. Inorder (all types of DFS) Preorder: “Visit” a node, then traverse its children Inorder: Traverse left child, “visit” node, then traverse right child Postorder: Traverse children, then “visit” node. Note: The prefix to order (pre, in, post) refers to when a node is visited with respect to its children ○ ex) That’s why postorder means that we visit the node AFTER we visit the children (post is a prefix, meaning “behind,” “after,”) Note: Node and vertex are used interchangeably. Q1.1: Graphs Give the DFS preorder, DFS postorder, and BFS order of the graph traversals starting from vertex A. Break ties alphabetically. Q1.1: Implementing Post/Preorder Maintain a stack of nodes and a marked set. As soon as we add something to our stack, we note it for preorder. The top node in our stack represents the node we are currently on, and the marked set represents nodes that have been visited. After we add a node to the

AI summary