Native lesson simulator
Graph traversal
Vertices connect through edges; traversal manages a frontier.
Start at A and enqueue neighbors B and C.
Use the playback controls inside the visual to step through the traversal frontier.
Flash cards
Review the key moves
What is the main idea behind DSA Graphs Implementation?
Lesson checks
Practice each idea before moving on
Short Mimo-style checks built from this lesson's code, terms, and sequence.
Which statement best captures the main point of this lesson?
Complete the missing token from the example code.
___ = [ 'A', 'B', 'C', 'D']Put the learning moves in the order that makes the concept easiest to apply.
A Basic Graph Implementation
Before we can run algorithms on a Graph, we must first implement it somehow.
To implement a Graph we will use an Adjacency Matrix , like the one below.
To store data for each vertex, in this case the letters A, B, C, and D, the data is put in a separate array that matches the indexes in the adjacency matrix, like this:
vertexData = [ 'A', 'B', 'C', 'D']For an undirected and not weighted Graph, like in the image above, an edge between vertices i and j is stored with value 1 . It is stored as 1 on both places (j,i) and (i,j) because the edge goes in both directions. As you can see, the matrix becomes diagonally symmetric for such undirected Graphs.
Let's look at something more specific. In the adjacency matrix above, vertex A is on index 0 , and vertex D is on index 3 , so we get the edge between A and D stored as value 1 in position (0,3) and (3,0) , because the edge goes in both directions.
Below is a basic implementation of the undirected Graph from the image above.
Example
vertexData = ['A', 'B', 'C', 'D']
adjacency_matrix = [
[0, 1, 1, 1], # Edges for A
[1, 0, 1, 0], # Edges for B
[1, 1, 0, 0], # Edges for C
[1, 0, 0, 0] # Edges for D
]
def print_adjacency_matrix(matrix):
print("\nAdjacency Matrix:")
for row in matrix:
print(row)
print('vertexData:',vertexData)
print_adjacency_matrix(adjacency_matrix)This implementation is basically just a two dimensional array, but to get a better sense of how the vertices are connected by edges in the Graph we have just implemented, we can run this function:
Example
def print_connections(matrix, vertices):
print("\nConnections for each vertex:")
for i in range(len(vertices)):
print(f"{vertices[i]}: ", end="")
for j in range(len(vertices)):
if matrix[i][j]: # if there is a connection
print(vertices[j], end=" ")
print() # new lineGraph Implementation Using Classes
A more proper way to store a Graph is to add an abstraction layer using classes so that a Graph's vertices, edges, and relevant methods, like algorithms that we will implement later, are contained in one place.
Programming languages with built-in object-oriented functionality like Python and Java, make implementation of Graphs using classes much easier than languages like C, without this built-in functionality.
Here is how the undirected Graph above can be implemented using classes.
Example
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
g = Graph(4)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_edge(0, 1) # A - B
g.add_edge(0, 2) # A - C
g.add_edge(0, 3) # A - D
g.add_edge(1, 2) # B - C
g.print_graph()In the code above, the matrix symmetry we get for undirected Graphs is provided for on line 9 and 10, and this saves us some code when initializing the edges in the Graph on lines 29-32.
Implementation of Directed and Weighted Graphs
To implement a Graph that is directed and weighted, we just need to do a few changes to previous implementation of the undirected Graph.
To create directed Graphs, we just need to remove line 10 in the previous example code, so that the matrix is not automatically symmetric anymore.
The second change we need to do is to add a weight argument to the add_edge() method, so that instead of just having value 1 to indicate that there is an edge between two vertices, we use the actual weight value to define the edge.
Below is the implementation of the directed and weighted Graph above.
Example
class Graph:
def __init__(self, size):
self.adj_matrix = [[None] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(lambda x: str(x) if x is not None else '0', row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
g = Graph(4)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_edge(0, 1, 3) # A -> B with weight 3
g.add_edge(0, 2, 2) # A -> C with weight 2
g.add_edge(3, 0, 4) # D -> A with weight 4
g.add_edge(2, 1, 1) # C -> B with weight 1
g.print_graph()Line 3: All edges are set to None initially.
Line 7: The weight can now be added to an edge with the additional weight argument.
Line 10: By removing line 10, the Graph can now be set up as being directed.
On the next lesson we will see how Graphs can be traversed, and on the next pages after that we will look at different algorithms that can run on the Graph data structure.