15. Graphs

Graph Theory is a branch of mathematics full of not just interesting theory, but a vast amount of computational work. A graph is a simple but powerful idea: a set of vertices (or nodes) connected by edges (or links). This flexible structure makes it the perfect tool for modeling a wide range of real-world systems, from social networks and website links to transportation logistics and molecular interactions. This chapter will cover the basics of the theory as well as actual hands-on computations. We’ll start by answering the first critical question: how do we represent a graph in a computer? We’ll implement our own graph data structure using adjacency lists, learn to create graphs programmatically, and write a custom plotting function to visualize our creations.

Once we have a way to build and see graphs, we can explore how to analyze them. We’ll cover the two most fundamental algorithms for “walking” through a graph: Depth First Search (DFS) and Breadth First Search (BFS). We’ll see how these two different strategies, one “plunging deep” and the other “exploring wide”, allow us to solve classic problems. We’ll implement them from scratch to find any path between two points and, more importantly, to find the shortest path. These algorithms are the essential building blocks for almost everything else you can do with graphs, from solving puzzles like mazes to powering GPS navigation.