Homework 6

Download the corresponding ipynb file here: hw-6.ipynb.

Graphs

Exercise 1 (10 points) We have already seen in Chapter 7 a Python implementation of the adjacency-list representation of graphs. Using the implementation or your own class, write a method for BFS, following the pseudocode from last lecture.

Exercise 2 (10 points) Given (the adjacency-list representation of) an undirected graph, develop an algorithm to find the number of connected components.

Exercise 3 (5 points) Discuss the time and space complexities of your algorithm for Exercise 2.

Exercise 4 (10 points) Given a an undirected graph, check if it contains a cycle. Implement your algorithm in Python.