The Self-Taught Computer Scientist

Chapter 16 Graphs
175
Many of these concepts should already be familiar to you because you’ve already learned about 
trees. A tree is a restricted form of a graph. Trees have direction (the parent- child relationship) and 
do not contain cycles, which makes them directed acyclic graphs with a restriction: a child can have 
only one parent.
Figure 16.4: A complete graph has connections among all vertices.
20
30
40
10
Figure 16.5: An incomplete graph has some connected vertices.
1
3
2
4
5
Figure 16.6: A graph path follows a specific sequence.

---

Data Structures
176
There are several ways to create graphs programmatically. For example, you can use an edge list, 
an adjacency matrix, or an adjacency list. An edge list is a data structure where you represent each 
edge in a graph with two vertices that connect. For example, Figure 16.8 is a graph with four vertices.
You can represent it with an edge list like this:
[
[10, 20]
[10, 30]
[20, 10]
[20, 30]
[30, 10]
[30, 20]
[30, 40]
[40, 30]
]
This edge list is a list of lists, and each list contains two vertices from the graph that connect.
You can also represent a graph with an adjacency matrix. An adjacency matrix is a two- dimensional 
array of rows and columns that contains a graph’s vertices. In an adjacency matrix, you use the inter-
section of each row and column to represent an edge. Traditionally, you use a 1 to represent vertices 
that connect and a 0 to show vertices that do not. When two vertices are connected, they are adjacent. 
Figure 16.9 shows how you represent the same graph with an adjacency matrix:
Figure 16.7: An example of a graph that contains a cycle
20
30
40
10