A graph is a data structure used to illustrate connections between two objects. A simple example of a graph is a geographical map in which different places are connected by roads. In this article, we will study the theoretical aspects of a graph data structure. Additionally, we will implement a graph using two different methods.
What is a graph?
A graph is a non-linear data structure that is used to represent interconnected objects. The objects are termed vertices and the link between them are called edges.
Mathematically, A graph G is defined as an ordered pair of two sets V and E. It is represented as G=(V,E) where,
- V is the set of vertices or vertices present in the graph.
- E is the set of edges present in the graph. Each edge is represented using a tuple which shows the vertices it is connected to. For example, if an edge ‘e’ is connecting vertices v1 and v2, it will be represented as (v1,v2).
To understand this more clearly, let’s look at the following example.
In the above figure, we have a graph containing 6 vertices namely 0,1,2,3,4,5. Thus the set V in the equation of G=(V, E) will be the set of vertices which will be represented as follows.
V={0,1,2,3,4,5}
To find the set E consisting of edges, we will first find each edge. In the figure above, we have 8 lines connecting different vertices of the graph.
We define each vertex “v” using the name of vertices they are connecting. For example, The edge connecting 0 to 1 will be termed as e01 and will be represented using the tuple (0,1). Similarly all the edges will be defined as follows.
e01=(0,1)
e12=(1,2)
e03=(0,3)
e13=(1,3)
e34=(3,4)
e25=(2,5)
e45=(4,5)
e24=(2,4)
The set E consisting of each edge in the graph will be defined as follows.
E={(0,1),(1,2),(0,3),(1,3),(3,4),(2,5),(4,5),(2,4)}.
As we have obtained the mathematical notation for the graph, we will now implement it in python.
How to implement a graph using an adjacency matrix in Python?
If we have a graph with N vertices, An adjacency matrix for the graph will be a N x N two-dimensional matrix. The rows and columns in the matrix represent the vertices of the graph and the values in the matrix determine whether there is an edge between two vertices or not.
Suppose we have the adjacency matrix A for any graph. For any index (i,j), If there is an edge between vertex i and vertex j, we assign value 1 to A[i][j]. When there is no edge present between vertices i and j, The value 0 is assigned to A[i][j]. This can be implemented in Python as follows.
import numpy as np
# keep vertices in a set
vertices = {0, 1, 2, 3, 4, 5}
# keep edges in a set
edges = {(0, 1), (1, 2), (0, 3), (1, 3), (3, 4), (2, 5), (4, 5), (2, 4)}
# create a 6X6 integer numpy array with all values initialised to zero
adjacencyMatrix = np.zeros((6, 6)).astype(int)
# Represent edges in the adjacency matrix
for edge in edges:
v1 = edge[0]
v2 = edge[1]
adjacencyMatrix[v1][v2] = 1
adjacencyMatrix[v2][v1] = 1 # if v1 is connected to v2, v2 is also connected to v1
print("The set of vertices of the graph is:")
print(vertices)
print("The set of edges of the graph is:")
print(edges)
print("The adjacency matrix representing the graph is:")
print(adjacencyMatrix)
Output:
The set of vertices of the graph is:
{0, 1, 2, 3, 4, 5}
The set of edges of the graph is:
{(0, 1), (2, 4), (1, 2), (3, 4), (0, 3), (4, 5), (2, 5), (1, 3)}
The adjacency matrix representing the graph is:
[[0 1 0 1 0 0]
[1 0 1 1 0 0]
[0 1 0 0 1 1]
[1 1 0 0 1 0]
[0 0 1 1 0 1]
[0 0 1 0 1 0]]
Implementation of a graph using an adjacency matrix has a drawback. Here, we assign memory for each vertex whether it is present or not. This can be avoided by implementing the graph using the adjacency list as discussed in the following section.
How to implement a graph using an adjacency list in Python?
An adjacency list stores a list of all connected vertices from each vertex. To implement this, we will use a dictionary in which each key of the dictionary represents a vertex and values for the keys contain a list of vertices the key vertex is connected to. This can be implemented as follows.
# keep vertices in a set
vertices = {0, 1, 2, 3, 4, 5}
# keep edges in a set
edges = {(0, 1), (1, 2), (0, 3), (1, 3), (3, 4), (2, 5), (4, 5), (2, 4)}
# create a dictionary with vertices of graph as keys and empty lists as values
adjacencyList={}
for vertex in vertices:
adjacencyList[vertex]=[]
# Represent edges in the adjacency List
for edge in edges:
v1 = edge[0]
v2 = edge[1]
adjacencyList[v1].append(v2)
adjacencyList[v2].append(v1) # if v1 is connected to v2, v2 is also connected to v1
print("The set of vertices of the graph is:")
print(vertices)
print("The set of edges of the graph is:")
print(edges)
print("The adjacency List representing the graph is:")
print(adjacencyList)
Output:
The set of vertices of the graph is:
{0, 1, 2, 3, 4, 5}
The set of edges of the graph is:
{(0, 1), (2, 4), (1, 2), (3, 4), (0, 3), (4, 5), (2, 5), (1, 3)}
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2]}
In the above output, we can see that each key is representing a vertex and every key is associated to a list of vertex it is connected to. This implementation is efficient than adjacency matrix representation of graph. This is because of the reason that we don’t need to store values for the edges which are not present.
Conclusion
In this article, we have studied the theoretical concepts for representing a graph and then we have implemented a graph using adjacency matrix and adjacency list representation in python. Stay tuned for more informative articles. Happy Learning.