The Self-Taught Computer Scientist

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

---

Data Structures
174
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 on Twitter, but he 
is not following you back. When you are drawing a directed graph, you typically represent the edges 
with arrows showing the direction you can move (Figure 16.2).
An undirected graph is one in which the edges are bidirectional, which means you can travel in 
either direction between two connected vertices. You can think of this as a two- way connection, such 
as the relationship between friends on a social network like Facebook. For example, if Logan is friends 
with Hadley on Facebook, then Hadley is friends with Logan. When you are drawing an undirected 
graph, you usually draw the edges without arrows (Figure 16.3).
A complete graph is one in which every vertex is connected to every other vertex (Figure 16.4).
In an incomplete graph, some but not all vertices are connected (Figure 16.5).
A graph path is a sequence of vertices connected by edges (Figure 16.6). For example, say you had 
a graph representing a city. A path between Los Angeles and San Francisco would be a series of edges 
(representing roads) you can use to travel from Los Angeles to San Francisco.
A cycle is a path in a graph starting and ending at the same vertex. An acyclic graph is a graph that 
does not contain a cycle. See Figure 16.7.
Figure 16.2: A directed graph moves in a specific direction.
1
2
3
4
5
7
6
Figure 16.3: An undirected graph can move in either direction.

---