In this homework, we will focus our attention to searching on graphs and finding minimum span-ning trees.
Problem 1: Graph Traversal 50 points
1. Demonstrate both breadth-first search (BFS) and depth-first search (DFS) algorithms (with v5 as the start node) on the graph shown in Figure 1. Clearly show how each node-attribute (including frontier) changes in each iteration in both the algorithms. (20 points)
2. Implement both BFS and DFS algorithms in Python, using an adjacency list representation for the graph shown in Figure 1. (30 points)
Figure 1: Example Graph for Search Algorithms
Part 4: Graph Algorithms: Part I 2
Problem 2: Minimum Spanning Trees 50 points
1. Demonstrate both Kruskal’s and Prim’s algorithm (with vertex v1 as the start node) for the petersen graph shown in Figure 2. (20 points)
2. Implement Prim’s algorithm in Python, using an adjacency matrix representation for the graph in Figure 2. (15 points)
Bonus Problem (10 points):
Implement Kruskal’s algorithm in Python with the disjoint set data structure discussed in the class, using an adjacency matrix representation for the graph in Figure 2.
Figure 2: Petersen Graph
