Graph Algorithms

In this chapter we discuss several common problems in graph theory. Not only are these algorithms useful in practice, they are interesting because in many real- life applications they are too slow unless careful attention is paid to the choice of data structures. We will

• Show several real-life problems, which can be converted to problems on graphs.

• Give algorithms to solve several common graph problems.

• Show how the proper choice of data structures can drastically reduce the running time of these algorithms.

• See an important technique, known as depth-first search, and show how it can be used to solve several seemingly nontrivial problems in linear time.