The Self-Taught Computer Scientist

16Graphs

Learning to code will be a huge booster for your future, no matter what your professional plans may be. Learning to code will also make you extremely cool!

Max Levchin

A graph is an abstract data type in which a piece of data connects to one or more other pieces of data. Each piece of data in a graph is called a vertex or a node. A vertex has a name called a key. A vertex can have additional data called its payload. The connection between vertices in a graph is called an edge. A graph's edges can contain a weight: the cost to travel between vertices. For example, if you created a graph representing the data in a map, each vertex could be a city, and the weight between two vertices could be the distance between them (Figure 16.1).

Figure 16.1 A graph contains vertices, edges, payloads, and weight.

There are several types of graphs, including directed graphs, undirected graphs, and complete graphs. A directed graph is one in which each edge has a direction associated with it, and you can move between two vertices only in that direction. The connection between two vertices is typically in one direction, but you can also make an edge a two-way connection. A directed graph is an excellent choice for creating a graph representing a social network with followers (like Twitter). For example, you could use a directed graph to represent that you are following Lebron James ...