Loading lesson path
Concept visual
Start from A
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. A B C D A B C D A B C D
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 . It is stored as
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 , and vertex D is on index , so we get the edge between A and D stored as value
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.
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:
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 lineA 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. A B C D A B C D A B C D
Here is how the undirected Graph above can be implemented using classes.
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]Formula
self.size = size self.vertex_data = [''] * sizedef 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] = 1def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = datadef 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}")Formula
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')
Formula
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 - Cg.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.
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
to indicate that there is an edge between two vertices, we use the actual weight value to define the edge. A B
C
D A B C D A B C D
A directed and weighted Graph, and its adjacency matrix. Below is the implementation of the directed and weighted Graph above.
class Graph:
def __init__(self, size):
self.adj_matrix = [[None] * size for _ in range(size)]Formula
self.size = size self.vertex_data = [''] * sizedef 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] = datadef 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}")Formula
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()
None initially.
The weight can now be added to an edge with the additional weight argument.
By removing line 10, the Graph can now be set up as being directed. On the next page 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.
How are the edges in a graph implemented? The edges, and edge weights, in a graph are normally implemented in an matrix. Submit Answer »