- 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.