Week 10: Optional Exercises

For all exercises this week, use the adjacency list graph representation discussed in the lecture.

1. Connected Graph

Write a function that takes a graph and returns true if the graph is connected.

2. Cyclic Graph

Write a function that takes a (possibly undirected) graph and returns true if the graph contains a cycle.

3. To Tree or Not to Tree

Write a function that takes an undirected graph and returns true if it is a tree.

4. Shortest Distance

Write a function that takes a graph and two vertex ids and returns an integer representing the length of the shortest path between the vertices.

5. King Passage

Write a program that reads a list of blocked squares on an 8 x 8 chessboard, plus a starting and ending position. The program should report whether it is possible for a king to travel from the starting to the ending position without passing through any blocked square.

6. King Distance

Modify the previous program to report the number of moves the king must make from the starting to the ending square.

7. King Path

Modify the previous program to print the actual path the king must take.