3. Consider the following undirected graph G, consisting of 9 nodes laid out in a 3-by-3...

Transcribed Image Text:

3. Consider the following undirected graph G, consisting of 9 nodes laid out in a 3-by-3 grid: 0 4 7 2 Algorithm 1 Problem 3 1: function MODIFIEDBFS(G = (V, E), s) 2: 3: 4: 5: 6: 7: 8: 9: 5 8 (3 Start searching at node 1, and break ties for exploring the next node based on lower numerical order (i.e. add nodes to a queue low to high, add nodes to a stack high to low). (a) In what order are nodes marked as explored by BFS? (b) In what order are nodes marked as explored by DFS? (c) Replace the queue with a stack in BFS, but do not change when nodes are explored as in DFS. In what order does this new search (Algorithm 1) mark nodes as explored? mark s as explored, all other nodes as unexplored let S be a stack, initialized with s while S is not empty do pop node v from S for each neighbor w of v do if w is unexplored then mark w as explored push w onto S 6 9 3. Consider the following undirected graph G, consisting of 9 nodes laid out in a 3-by-3 grid: 0 4 7 2 Algorithm 1 Problem 3 1: function MODIFIEDBFS(G = (V, E), s) 2: 3: 4: 5: 6: 7: 8: 9: 5 8 (3 Start searching at node 1, and break ties for exploring the next node based on lower numerical order (i.e. add nodes to a queue low to high, add nodes to a stack high to low). (a) In what order are nodes marked as explored by BFS? (b) In what order are nodes marked as explored by DFS? (c) Replace the queue with a stack in BFS, but do not change when nodes are explored as in DFS. In what order does this new search (Algorithm 1) mark nodes as explored? mark s as explored, all other nodes as unexplored let S be a stack, initialized with s while S is not empty do pop node v from S for each neighbor w of v do if w is unexplored then mark w as explored push w onto S 6 9

Answer rating: 100% (QA)

a BFS explores nodes in the order 1 2 4 3 ... View the full answer