13 Graphs: Learning how to model complex relationships in data
In this chapter
- defining graphs
- discussing the basic properties of graphs
- evaluating graph implementation strategies: adjacency list and adjacency matrix
- exploring graph traversal: breadth-first search and depth-first search
In our final chapter, we discuss another data structure that exceeds the characteristics of a container—graphs. They can be used to store elements, but that would be an understatement as graphs have a much broader range of applications.
This chapter defines what graphs are and discusses some of their most important properties. After covering the basics, we move on to their implementation. Finally, we briefly discuss two methods for traversing a graph.
What’s a graph?
Not surprisingly, the first question we want to answer is, “What is a graph?” There are many ways to define graphs, ranging from informal definitions to rigid theory. I’ll start with this definition: graphs are a generalization of trees. When I introduced trees in chapter 11, I told you that they can be used to model hierarchical relationships. Graphs allow you to model more general relationships. For example, the structure of your file system or an arithmetic expression can be represented using trees, but trees are not suitable to represent a friendship graph or the flow of a computer program. For these kinds of relationships, we need graphs.