# 14 An introduction to graphs: Finding paths of minimum distance

### This chapter covers

• Introducing graphs from a theoretical point of view
• Learning strategies for implementing graphs
• Finding the best route for deliveries
• Introducing search algorithms on graphs: BFS and DFS
• Using BFS to find the route that traverses the fewest blocks
• Finding the shortest route with Dijkstra’s minimum distance algorithm
• Finding the quickest route with A* algorithm for optimal search

We already described the basics of trees in appendix C and used several kinds of trees in the previous chapters: binary search trees, heaps, k-d trees, and so on. You should now be familiar with them. Graphs could be considered a generalization of trees, although in reality the opposite is true, and it is trees that are a special case of graphs. A tree, in fact, is a connected, acyclic undirected graph. Figure 14.1 shows an example of two graphs, only one of which is a tree. Don’t worry if you are not sure which one, because in this chapter we’ll take a closer look at the meaning of those properties in the definition of trees, and they will help us to better explain graphs’ properties and make sense of these examples.

##### Figure 14.1 Two graphs, only one of which is also a tree. Can you tell which one?

But to do so we need to follow a meaningful order and so, we first need to give a formal definition of graphs and understand how we can represent them.