The graph search algorithms are important in Al. This assignment considers the following uninformed graph search algorithms in a given graph. 1. Breadth First Search (BFS) (2 points) 2. Depth First Search (DFS) (2 points) 3. Iterative Deepening Search (IDS) (2 points) 4. Uniform Cost Search (UCS) (2 points) Your task is to implement the above algorithms to find the traversal path and exact path of any given graph (State Space Graph). You can use any programming language. Hint: A state-space graph can be represented as a search tree; the start state is the root node, and children correspond to successors. There are two popular options for representing a graph: adjacency matrix and adjacency list. You can insert the given graph using either of these options. Using an adjacency list is easy for smaller graph representation. Consider the following two graphs to test your algorithms: 5 A 6 D 3 5 S S 3 B 6 D 1 4 6 4 3 1 3 4 2 10 7 2 6 B E 6 Graph a Graph b Sample Output of Graph a: BFS: Traversal path: SABBDCDCDG Exact path: SADG DFS: Traversal path: SABCDG Exact path: SABCDG IDS: Traversal path: SSAB SABDBCD SABCDDG Exact path: SADG UCS: Traversal path: SBABCDG Exact path: SBDG Part 1: (Points 2) Implement the algorithms in the first part on a randomly generated space graph. To generate a random space graph, you can send two parameters to decide the number of edges and number of nodes. Then you can set the start and goal state. The graph search algorithms are important in Al. This assignment considers the following uninformed graph search algorithms in a given graph. 1. Breadth First Search (BFS) (2 points) 2. Depth First Search (DFS) (2 points) 3. Iterative Deepening Search (IDS) (2 points) 4. Uniform Cost Search (UCS) (2 points) Your task is to implement the above algorithms to find the traversal path and exact path of any given graph (State Space Graph). You can use any programming language. Hint: A state-space graph can be represented as a search tree; the start state is the root node, and children correspond to successors. There are two popular options for representing a graph: adjacency matrix and adjacency list. You can insert the given graph using either of these options. Using an adjacency list is easy for smaller graph representation. Consider the following two graphs to test your algorithms: 5 A 6 D 3 5 S S 3 B 6 D 1 4 6 4 3 1 3 4 2 10 7 2 6 B E 6 Graph a Graph b Sample Output of Graph a: BFS: Traversal path: SABBDCDCDG Exact path: SADG DFS: Traversal path: SABCDG Exact path: SABCDG IDS: Traversal path: SSAB SABDBCD SABCDDG Exact path: SADG UCS: Traversal path: SBABCDG Exact path: SBDG Part 1: (Points 2) Implement the algorithms in the first part on a randomly generated space graph. To generate a random space graph, you can send two parameters to decide the number of edges and number of nodes. Then you can set the start and goal state