# 9.26. Programming Exercises

- Modify the depth first search function to produce a topological sort.
- Modify the depth first search to produce strongly connected
components.
- Write the
`transpose`

method for the `Graph`

class.
- Using breadth first search write an algorithm that can determine the
shortest path from each vertex to every other vertex. This is called
the all pairs shortest path problem.
- Using breadth first search revise the maze program from
the recursion chapter to find the shortest path out of a maze.
- Write a program to solve the following problem: You have two jugs, a
4-gallon and a 3-gallon. Neither of the jugs has markings on them.
There is a pump that can be used to fill the jugs with water. How can
you get exactly two gallons of water in the 4 gallon jug?
- Generalize the problem above so that the parameters to your solution
include the sizes of each jug and the final amount of water to be
left in the larger jug.
- Write a program that solves the following problem: Three missionaries
and three cannibals come to a river and find a boat that holds two
people. Everyone must get across the river to continue on the
journey. However, if the cannibals ever outnumber the missionaries on
either bank, the missionaries will be eaten. Find a series of
crossings that will get everyone safely to the other side of the
river.