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.

14.1 Definitions

14.1.1 Implementing graphs

14.1.2 Graphs as algebraic types

14.1.3 Pseudo-code

14.2 Graph properties

14.2.1 Undirected

14.2.2 Connected

14.2.3 Acyclic

14.3 Graph traversal: BFS and DFS

14.3.1 Optimizing delivery routes

14.3.2 Breadth first search

14.3.3 Reconstructing the path to target

14.3.4 Depth first search

14.3.5 It’s queue vs stack again

14.4 Shortest path in weighted graphs: Dijkstra

sitemap