Description
Introduction In this programming assignment, you will be tasked with implementing two fundamental graph search algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS). These algorithms will be applied to a given graph topology to find the path from a start node ’S’ to a goal node ’G’. Exercise 1 Implement a Depth-First Search algorithm to find the path from the start node ’S’ to the goal node ’G’. Please consider the topology that is shared in Figure 1. • Your implementation should correctly navigate this graph using DFS to find a path from ’S’ to ’G’. • Your DFS algorithm should output the path from ’S’ to ’G’ as a sequence of nodes. • Include comments and clear documentation in your code for clarity. • Ensure that your code is well-structured and follows best coding practices. 1 Figure 1: Graph topology. Exercise 2 Implement a Breadth-First Search algorithm to find the path from the start node ’S’ to the goal node ’G’. You are provided with the same graph topology as in Task 1. • Your implementation should correctly navigate this graph using BFS to find a path from ’S’ to ’G’. • Your BFS algorithm should output the path from ’S’ to ’G’ as a sequence of nodes. • Include comments and clear documentation in your code for clarity. • Ensure that your code is well-structured and follows best coding practices. 2 Submission Guidelines • Each student must submit their assignment individually. • Submit your assignment as a PDF file. • The PDF file should include BOTH Code for both Task 1 (DFS) and Task 2 (BFS) AND screenshots demonstrating the execution of your code on the provided graph topology, showing the path from ’S’ to ’G’. • Ensure that your code and screenshots are clearly labeled and organized within the PDF.