The Self-Taught Computer Scientist

Figure 16.9: An adjacency matrix of the graph in Figure 16.8

---

Data Structures
178
use graphs to create maps with each vertex representing cities and other destinations and edges
representing roads, bus routes, or air routes between those destinations. Programmers also use graphs 
to find the fastest path between destinations. They are also helpful for computer graphics. You can 
use the vertices and edges of graphs to represent the points, lines, and planes of 2D and 3D shapes 
(Figure 16.10).
Search engine algorithms often use graphs to help determine search ranking based on the connec-
tivity of the search and results. Operating systems and programming language systems also use graphs 
in memory management.
Creating a Graph
Here is how to create an adjacency list in Python:
class Vertex:
def __init__(self, key):
self.key = key
self.connections = {}
def add_adj(self, vertex, weight=0):
self.connections[vertex] = weight
def get_connections(self):
return self.connections.keys()
def get_weight(self, vertex):
return self.connections[vertex]
class Graph:
def __init__(self):
self.vertex_dict = {}
def add_vertex(self, key):
new_vertex = Vertex(key)
Figure 16.10: Graphs can represent 3D shapes.

---

Chapter 16 Graphs
179
self.vertex_dict[key] = new_vertex
def get_vertex(self, key):
if key in self.vertex_dict:
return self.vertex_dict[key]
return None
def add_edge(self, f, t, weight=0):
if f not in self.vertex_dict:
self.add_vertex(f)
if t not in self.vertex_dict:
self.add_vertex(t)
self.vertex_dict[f].add_adj(self.vertex_dict[t], weight)
First, you define a vertex class, as you did earlier with nodes when you created linked lists:
class Vertex:
def __init__(self, key):
self.key = key
self.connections = {}
def add_adj(self, vertex, weight=0):
self.connections[vertex] = weight
Your 
Vertex
class has two instance variables: 
self.key
and 
self.connections
. The first variable, 
key
, represents the vertex’s key, and the second variable, 
connections
, is a dictionary where you will 
store the vertices each vertex is adjacent to.
def __init__(self, key):
self.key = key
self.connections = {}
Your 
Vertex
class has a method called 
add_adj
that accepts a vertex as a parameter and makes it 
adjacent to the vertex you called the method on by adding the connection to 
self.connections
. The 
method also accepts a weight as a parameter if you want to add a weight to the relationship.
def add_adj(self, vertex, weight=0):
self.connections[vertex] = weight
Next, you define a class called 
Graph
. 
Graph
has an instance variable 
self.vertex_dict
that stores 
the vertices in each graph.
def __init__(self):
self.vertex_dict = {}
Your class’s method 
add_vertex
adds a new vertex to a graph by first creating a vertex and then 
mapping the key the user passes in as a parameter to the new vertex inside 
self.vertex_dict
.

---