Let's solve each question step by step: --- ## **Question 1: Undirected Graph** ### **a. Depth-First Search (DFS) from vertex 0** **Adjacency lists:** - 0: 1, 2, 6 - 1: 0, 2, 6 - 2: 0, 1, 3, 6 - 3: 2, 7, 8, 9 - 4: 5, 7 - 5: 4, 8 - 6: 0, 1, 2, 7 - 7: 3, 4, 6, 9 - 8: 3, 5, 9 - 9: 3, 7, 8 #### **DFS Steps (starting from 0, visit lower numbered vertices first):** 1. Start at 0. Visit 0. 2. From 0, go to 1 (next lowest). 3. From 1, go to 2 (next lowest unvisited). 4. From 2, go to 3 (next lowest unvisited). 5. From 3, go to 7 (next lowest unvisited). 6. From 7, go to 4 (next lowest unvisited). 7. From 4, go to 5 (next lowest unvisited). 8. From 5, go to 8 (next lowest unvisited). 9. From 8, go to 9 (next lowest unvisited). 10. All neighbors of 9 are visited. **DFS Order:** **0-1-2-3-7-4-5-8-9-6** But let's check if 6 is reached earlier: - From 0, after 1, before 2, 6 is also an option. But since adjacency lists are in sorted order, 1 comes before 2 and 6, so we visit 1, then 2, then 3, etc. **Final DFS Order:** **0-1-2-3-7-4-5-8-9-6** --- ### **b. Breadth-First Search (BFS) from vertex 0** **BFS Steps:** 1. Start at 0. Visit 0. 2. Visit 0's neighbors in sorted order: 1, 2, 6. 3. Visit 1's neighbors: 0, 2, 6 (already visited). 4. Visit 2's neighbors: 0, 1, 3, 6 (3 is unvisited, visit 3). 5. Visit 6's neighbors: 0, 1, 2, 7 (7 is unvisited, visit 7). 6. Visit 3's neighbors: 2, 7, 8, 9 (8 and 9 are unvisited, visit 8, then 9). 7. Visit 7's neighbors: 3, 4, 6, 9 (4 is unvisited, visit 4). 8. Visit 8, 9, 4, 5 (visit 5 from 4, as 5 is unvisited). **BFS Order:** **0-1-2-6-3-7-8-9-4-5** --- ## **Question 2: Directed Graph** ### **a. Depth-First Search (DFS) from vertex 0** **DFS Steps:** 1. Start at 0. Visit 0. 2. From 0, go to 1 (next lowest unvisited). 3. From 1, go to 2 (next lowest unvisited). 4. From 2, go to 3 (next lowest unvisited). 5. From 3, go to 7 (next lowest unvisited). 6. From 7, go to 4 (next lowest unvisited). 7. From 4, go to 5 (unvisited). 8. From 5, go to 8 (unvisited). 9. From 8, go to 9 (unvisited). 10. From 9, go to 6 (unvisited). **DFS Order:** **0-1-2-3-7-4-5-8-9-6** --- ### **b. Breadth-First Search (BFS) from vertex 0** **BFS Steps:** 1. Start at 0. Visit 0. 2. Visit 0's neighbors: 1, 2, 6 (in order). 3. Visit 1's neighbor: 2. 4. Visit 2's neighbor: 3. 5. Visit 6's neighbor: 7. 6. Visit 3's neighbors: 7, 8, 9 (8 and 9 are unvisited). 7. Visit 7's neighbors: 4, 9 (4 is unvisited). 8. Visit 8's neighbor: 5 (5 is unvisited). 9. Visit 9's neighbor: 4 (already visited). 10. Visit 4, 5 (already visited). **BFS Order:** **0-1-2-6-3-7-8-9-4-5** --- ## **Summary of Answers:** ### **Question 1:** - **(a) DFS:** `0-1-2-3-7-4-5-8-9-6` - **(b) BFS:** `0-1-2-6-3-7-8-9-4-5` ### **Question 2:** - **(a) DFS:** `0-1-2-3-7-4-5-8-9-6` - **(b) BFS:** `0-1-2-6-3-7-8-9-4-5` --- **Let me know if you need a step-by-step trace for each vertex!**