Daily Python
Published in

Daily Python

Implementing basic Data Structures in Python — Part 2| Daily Python #16

This article is a tutorial that covers the implementation of basic data structures — Graphs and Trees. This article is in continuation with Daily Python #12, which covers — LinkedList, Stack, and Queue.

This article is a part of Daily Python challenge that I have taken up for myself. I will be writing short python articles daily.

There are no additional requirements for this article.

Graphs

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. Formally a Graph can be defined as — A Graph consists of a finite set of vertices(or nodes) and set of Edges that connect a pair of nodes.

In the above Graph, the set of vertices V = {0,1,2,3,4} and the set of edges E = {01, 12, 23, 34, 04, 14, 13}.

Two most commonly used representations of Graphs:

  1. Adjacency Matrix
  2. Adjacency List

We will cover both of these representations in this article.

Adjacency Matrix

It is a 2D array of size V x V where V is the number of vertices in a graph.
Let the 2D array be matrix[][], a slot matrix[i][j] = 1 indicates that there is an edge from vertex i to vertex j.

The adjacency matrix for an undirected graph is always symmetric.
Adjacency Matrix is also used to represent weighted graphs. If matrix[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

Adjacency List

An array of lists is used. The size of the array is equal to the number of vertices. Let the array be an array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs.

Following is the adjacency list representation of the above graph.

Let’s define a class Graph that will implement both of the above representations

class Graph:    def __init__(self,totalNodes):
self.totalNodes = totalNodes
self.adjMatrix = []
self.adjList = []
def acceptAdjMatrix(self):
print('The total number of nodes : ',self.totalNodes)
for row in range(self.totalNodes):
temp = list(map(int,input('Enter Row ' +str(row)+' of matrix : ').split(' ')))
self.adjMatrix.append(temp)

def printAdjMatrix(self):
if len(self.adjMatrix) == 0:
print('Please fill the Adjacency Matrix')
return
print('Given Adjacency Matrix :')
for row in self.adjMatrix:
print(row)
def acceptAdjList(self):
print('The total number of nodes : ',self.totalNodes)
print('Nodes : ',list(range(self.totalNodes)))
for node in range(self.totalNodes):
temp = list(map(int,input('Enter Adjacent Nodes of Node' +str(node)+' : ').split(' ')))
self.adjList.append(temp)
def printAdjList(self):
if len(self.adjList) == 0:
print('Please fill the Adjacency List')
return
print('\n\nGiven Adjacency List :')
for i in range(self.totalNodes):
print(i,end='--> ')
for j in self.adjList[i]:
print(j,end=' ')
print('')

The above code snippet has the basic functions of accepting the Adjacency Matrix and the Adjacency List, and also printing these two representations.

graph = Graph(5)
graph.acceptAdjMatrix()
graph.printAdjMatrix()
graph.acceptAdjList()
graph.printAdjList()
Snip of the Output of the above code snippet

There are multiple ways to traverse the graphs, one such method is Breadth-First Search Traversal

BFS in action
    def BFS(self):
iterator = 0
queue = [iterator]
visited = [0]*self.totalNodes
visited[iterator] = 1
while len(queue)>0:
queue.extend([ node for node in self.adjList[iterator] if visited[node] != 1 and node not in queue])
print(queue[0],end=' ')
visited[iterator] = 1
iterator = queue[0]
queue = queue[1:]
print('')
Snip of the Output of the above code

Trees

A tree is a widely used abstract data type (ADT) that simulates a hierarchical tree structure, with a root value and sub-trees of children with a parent node, represented as a set of linked nodes.

A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root.

Binary Search Tree

The most common representation of a tree is the Binary Search Tree

Binary Search Tree is a node-based binary tree data structure which has the following properties:

  • The left subtree of a node contains only nodes with keys lesser than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • The left and right subtree each must also be a binary search tree.

Let’s define a class for a simple Node that will be the basic element of the tree

class Node:

def __init__(self,value):
self.value = value
self.rightNode = None
self.leftNode = None

Let’s define a class for the Binary Search Tree

class BSTree:  def __init__(self):
self.headNode = None
def insertNode(self,value):
node = Node(value)
if self.headNode == None:
self.headNode = node
print(value,' inserted successfully')
else:
iterator = self.headNode
while True:
if value < iterator.value:
if iterator.leftNode == None:
iterator.leftNode = node
break
else:
iterator = iterator.leftNode
else:
if iterator.rightNode == None:
iterator.rightNode = node
break
else:
iterator = iterator.rightNode
print(value,' inserted successfully')
def printTree(self):
print('\n\nPreOrder Traversal (Root, Left, Right)')
self.preOrder(self.headNode)

print('\n\nInOrder Traversal (Left, Root, Right)')
self.inOrder(self.headNode)

print('\n\nPostOrder Traversal (Left, Right, Root)')
self.postOrder(self.headNode)

def inOrder(self,node):
if node == None:
return
self.inOrder(node.leftNode)
print(node.value, end=' ')
self.inOrder(node.rightNode)
def preOrder(self,node):
if node == None:
return
print(node.value, end=' ')
self.preOrder(node.leftNode)
self.preOrder(node.rightNode)
def postOrder(self,node):
if node == None:
return
self.postOrder(node.leftNode)
self.postOrder(node.rightNode)
print(node.value, end=' ')

Depth First Traversals:

1. Inorder (Left, Root, Right)
2. Preorder (Root, Left, Right)
3. Postorder (Left, Right, Root)

Let’s test the above code by inserting few values in the tree and traverse it

tree = BSTree()
tree.insertNode(5)
tree.insertNode(3)
tree.insertNode(1)
tree.insertNode(4)
tree.insertNode(6)
tree.printTree()
Snip of the Output of the above code snippet

I hope this article was helpful, do leave some claps if you liked it.

Follow the Daily Python Challenge here:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store