Depth First Search and Breadth First Search implementation in Python

Graph in Python can be created with:

	from collections import defaultdict
	class Graph:
	def __init__(self):
	self.graph = defaultdict(set)
	def add_links(self,a,b):
	self.graph[a].add(b)
	def get_graph(self):
	return self.graph
	if __name__ == '__main__':
	g=Graph()
	g.add_links(0,1)
	g.add_links(0,2)
	g.add_links(1,2)
	g.add_links(2,3)
	g.add_links(3,3)
	g.add_links(2,0)
	value = g.get_graph()
	Depth first search(DFS) can be implemented in the above graph with simple addition of
	DFS function as below
	from collections import defaultdict
	class Graph:
	def __init__(self):
	self.graph = defaultdict(set)
	def add_links(self,a,b):
	self.graph[a].add(b)
	def get_graph(self):
	return self.graph
	def DFS(self,source,visited):
	visited[source]=True print(source)
	for i in self.graph[source]:
	if(visited[i]==False):
	self.DFS(i,visited)
	if __name__ == '__main__':
	g=Graph()
	g.add_links(0,1)
	g.add_links(0,2)
	g.add_links(1,2)
	g.add_links(2,3)
	g.add_links(3,3)
	g.add_links(2,0)
	value = g.get_graph()
	print (value)
	visited = [False]*len(value)
	g.DFS(2,visited)
	Breadth First Search:
	from collections import defaultdict
	class Graph:
	def __init__(self):
	self.graph = defaultdict(set)
	def add_links(self,a,b):
	self.graph[a].add(b)
	def get_graph(self):
	return self.graph
	def BFS(self,source,visited):
	queue =[]
	queue.append(source)
	visited[source]=True while queue:
	value = queue.pop(0)
	print(value)
	for i in self.graph[value]:
	if(visited[i] == False):
	queue.append(i)
	visited[i]=True
	if __name__ == '__main__':
	g=Graph()
	g.add_links(0,1)
	g.add_links(0,2)
	g.add_links(1,2)
	g.add_links(2,3)
	g.add_links(3,3)
	g.add_links(2,0)
	value = g.get_graph()
	print (value)
	visited = [False]*len(value)
	g.BFS(2,visited)

view raw DFS_BFS_Py.py hosted with ❤ by GitHub

Merge sort and quick sort in python

Merge Sort:

def merge_sort(sor):
    mid = len(sor)//2    

    if(len(sor)<=1):

        return sor


    left =merge_sort(sor[0:mid])
    right = merge_sort(sor[mid:])
    i=j=0 

    tar =0   

    while(i<len(left) and j<len(right)):
        if(left[i]<right[j]):
            sor[tar]=left[i]
            i = i+1        

        else:
            sor[tar] =right[j]
            j=j+1 

        tar =tar+1    

    while(i<len(left)):
        sor[tar] =left[i]
        i =i +1        

        tar=tar+1    

    while(j<len(right)):
        sor[tar]= right[j]
        j=j+1        

        tar =tar+1
    return sor


if __name__ =='__main__':
    arr = [150,4,9,26,1,5,65,2,12,1,1]
    final =merge_sort(arr)
    print (final)

Quick Sort:

def partition(arr,l,h):
    # Note for finding the pivot element and placing the pivot element in middle    
    #  start from initial index and then increase one pointer j to teh last greatest element 
   #   if small element is found swap small element with bigger that is pointed by the j pointer 
   #   
    pivot = arr[h]
    j=l
    for i in range(l,h):
        if(arr[i]<pivot):
            arr[i],arr[j]=arr[j],arr[i]
            j=j+1    arr[j],arr[h]=arr[h],arr[j]
    return  j

def quick_sort(arr,l,h):
    if(l<h):
        pivot = partition(arr,l,h)
        quick_sort(arr,l,pivot-1)
        quick_sort(arr,pivot+1,h)


if __name__ =='__main__':
    arr = [150,4,9,26,8,100,80,12]
    n= len(arr)
    quick_sort(arr,0,n-1)
    print (arr)

Binary tree creation and inorder,preorder traversal both iterative and recurrence in python

class node:
    def __init__(self,key):
        self.data=key
        self.left= None

        self.right =None
def insert(root,nd):
    if(nd.data <= root.data):
        if(root.left is None):
            root.left = nd
        else:
            insert(root.left,nd)
    else:
        if(root.right is None):
            root.right = nd
        else:
            insert(root.right,nd)
def bin_search(root,key):
    if(root is None or root.data == key):
        return root
    else:
        if(key<root.data):
            return bin_search(root.left,key)
        else:
            return bin_search(root.right,key)


def tree_inorder_traverse(node):
    if(node == None):
        return    tree_inorder_traverse(node.left)
    print(node.data)
    tree_inorder_traverse(node.right)

def inorder_iterative(node):
    stack = []
    current = node
    while(1):
        if(current is not None):
            stack.append(current)
            current = current.left
        else:
            if(len(stack)>0):
                current = stack.pop()
                print(current.data)
                current = current.right
            else:
                break
def preorder_traversal(node):
    if(node == None):
        return    print(node.data)
    preorder_traversal(node.left)

    preorder_traversal(node.right)

def preorder_iterative(root):
    stack_pre=[]
    current = root
    while(1):
        if(current is not None):
            print(current.data)
            stack_pre.append(current)
            current =current.left
        else:
            if(len(stack_pre)>0):
                current = stack_pre.pop()
                current = current.right

            else:
                break

def preorder_iterative2(root):
    stack_pre=[]
    current = root
    stack_pre.append(current)
    while(len(stack_pre)>0):
        current = stack_pre.pop()
        print (current.data)
        if(current.right is not None):
            stack_pre.append(current.right)
        if(current.left is not None):
            stack_pre.append(current.left)


if __name__ == "__main__":
    root = node(50)
    insert(root,node(20))
    insert(root,node(70))
    insert(root,node(10))
    insert(root,node(30))
    insert(root,node(60))
    preorder_traversal(root)
    value = bin_search(root,20)
    print (value.data)

    print ("iterative")
    preorder_iterative(root)