# Graphs Data Structure in Python

Manav Narula Feb 15, 2022

In Programming, the graph data structure represents a set of interlinked objects. Every object is called the vertex, and the link is termed as edge.

In the above figure, `{A, B, C, D, E}` are the vertices, and the set is represented using the `V` symbol. The set of edges is represented using `E` and in the above example it is `{ad,ac,ab,cd,bd,be,de}`.

We can categorize graphs based on different criteria. First, we have graphs based on direction.

These are the undirected and directed graphs. In an undirected graph, edges have no direction.

This means the edge `ab` is the same as `ba`. The opposite is true for directed graphs where every edge has direction or orientation.

Based on weights, we have weighted and non-weighted graphs. Weighted graphs have some value associated with the edges.

There are also special graphs like trees, directed acyclic graphs, and more. Due to their non-linear nature, graphs have a lot of real-world applications.

Google maps use graphs for their transportation systems, and even Facebook uses graphs to visualize a user and its friend list.

In this tutorial, we will discuss representing a simple graph in Python.

## Use the Adjacency List to Implement Graphs in Python

An adjacency list stores every vertex and its adjacent vertices to visualize a graph. This can be represented using a dictionary.

Every vertex will be the dictionary’s key, and the corresponding value of the keys will contain the adjacent vertices in a list.

``````adjacency_lst = {}
mylst = []

def graph_node(node):
if node not in mylst:
mylst.append(node)
else:
print("The given node exists")

def graph_edge(node1, node2):
temp = []
if node1 in mylst and node2 in mylst:
temp.append(node2)

temp.append(node2)

else:
print("The given node does not exist")

def disp_graph():
print(node, " -> ", [i for i in adjacency_lst[node]])

graph_node('a')
graph_node('b')
graph_node('c')
graph_node('d')
graph_edge('a','b')
graph_edge('b','c')
graph_edge('c','d')
graph_edge('d','a')
disp_graph()
``````

Output:

``````a  ->  ['b']
b  ->  ['c']
c  ->  ['d']
d  ->  ['a']
{'a': ['b'], 'b': ['c'], 'c': ['d'], 'd': ['a']}
``````

We implement a simple graph using the adjacency list in the above example. At the start, the `adjacency_lst` dictionary is defined to store the nodes and edges.

The `graph_node()` function adds a vertex to this dictionary and checks if a node already exists. We add edges using the `graph_edge()` function.

The `disp_graph()` function displays this graph by displaying the nodes’ edges.

## Use the Adjacency Matrix to Implement Graphs in Python

We can use a matrix to represent a graph. A matrix is a 2-Dimensional array.

In an adjacency matrix, the value at a particular row and column indicates whether an edge exists or not.

If `A[i][j]` is 0, then no edge between `i` and `j`. A value of 1 indicates that the edge exists.

``````def graph_node(v):
global graph
global nodes_no
global nodes
if v in nodes:
else:
nodes_no = nodes_no + 1
nodes.append(v)
if nodes_no > 1:
for vertex in graph:
vertex.append(0)
temp = []
for i in range(nodes_no):
temp.append(0)
graph.append(temp)

def graph_edge(v1, v2, e):
global graph
global nodes_no
global nodes
if v1 not in nodes:
print("Node ", v1, " does not exist.")
elif v2 not in nodes:
print("Node ", v2, " does not exist.")
else:
index1 = nodes.index(v1)
index2 = nodes.index(v2)
graph[index1][index2] = e

def disp_graph():
global graph
global nodes_no
for i in range(nodes_no):
for j in range(nodes_no):
if graph[i][j] != 0:
print(nodes[i], " -> ", nodes[j], "Weight for the edge: ", graph[i][j])

nodes = []
nodes_no = 0
graph = []
graph_node(1)
graph_node(2)
graph_node(3)
graph_node(4)
graph_edge(1, 2, 1)
graph_edge(1, 3, 1)
graph_edge(2, 3, 0)
graph_edge(3, 1, 2)
disp_graph()
print("Matrix Representation: ", graph)
``````

Output:

``````1  ->  2 Weight for the edge:  1
1  ->  3 Weight for the edge:  1
3  ->  1 Weight for the edge:  2
Matrix Representation:  [[0, 1, 1, 0], [0, 0, 0, 0], [2, 0, 0, 0], [0, 0, 0, 0]]
``````

In the above example, we implement a graph using the adjacency matrix. We maintain the graph is a list of lists called `graph`.

The `graph_node()` function adds a vertex to the graph, and the edges between vertices are added.

Using the `graph_edge()` function. The `disp_graph()` displays the representation of nodes and edges from the matrix.

Author: Manav Narula

Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.