graph search algorithms

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.

CS5700 – Project Assignment 1
Graph Search Algorithms
September 1, 2023
Deadline: Sunday, September 10th, by midnight
Submission Format: PDF file containing code and screenshots
Late Submissions: No late submissions will be accepted
Accepted Programming Languages: Java, Python, C, or C++
Work Ethic: Academic integrity is of utmost importance. Each student is expected to complete this assignment independently, without seeking help from other students or external
individuals, including engineers or professionals. Any violation of this code of honesty will be
taken seriously and may result in penalties in accordance with the rules and regulations of the
University of Central Missouri.
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.
• Submit your assignment by the specified deadline. Late submissions will not be accepted.
Evaluation Criteria
Your assignment will be evaluated based on the following criteria:
• Correctness of your DFS and BFS implementations.
• Efficiency and clarity of your code.
• Proper documentation and comments.
• The accuracy of the path found from ’S’ to ’G’.
• Adherence to the submission format and deadline.
3