Posts

DFS in python

# Python3 program to print DFS traversal # from a given given graph from collections import defaultdict # This class represents a directed graph using # adjacency list representation class Graph: # Constructor def __init__(self): # default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self, u, v): self.graph[u].append(v) # A function used by DFS def DFSUtil(self, v, visited): # Mark the current node as visited # and print it visited[v] = True print(v, end = ' ') # Recur for all the vertices # adjacent to this vertex for i in self.graph[v]: if visited[i] == False: self.DFSUtil(i, visited) # The function to do DFS traversal. It uses # recursive DFSUtil() def DFS(self, v): # Mark all the vertices as not visited visited = [False] * (len(self.graph)) # Call the recursive helper function # to print DFS traversal self.DFSUtil(v, visited) #
Post a Comment
Read more

BFS in Python

Breadth First Search in Python # Python3 Program to print BFS traversal # from a given source vertex. BFS(int s) # traverses vertices reachable from s. from collections import defaultdict # This class represents a directed graph # using adjacency list representation class Graph: # Constructor def __init__(self): # default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): # Mark all the vertices as not visited visited = [False] * (len(self.graph)) # Create a queue for BFS queue = [] # Mark the source node as # visited and enqueue it queue.append(s) visited[s] = True while queue: # Dequeue a vertex from # queue and print it s = queue.pop(0) print (s, end = " ") # Get all adjacent vertices of the # dequeued vertex s. If a adjacent # has not been
Post a Comment
Read more

Merge Sort in Python

def mergeSort(nlist):     print("Splitting ",nlist)     if len(nlist)>1:         mid = len(nlist)//2         lefthalf = nlist[:mid]         righthalf = nlist[mid:]         mergeSort(lefthalf)         mergeSort(righthalf)         i=j=k=0         while i < len(lefthalf) and j < len(righthalf):             if lefthalf[i] < righthalf[j]:                 nlist[k]=lefthalf[i]                 i=i+1             else:                 nlist[k]=righthalf[j]                 j=j+1             k=k+1         while i < len(lefthalf):             nlist[k]=lefthalf[i]             i=i+1             k=k+1         while j < len(righthalf):             nlist[k]=righthalf[j]             j=j+1             k=k+1     print("Merging ",nlist) nlist = [14,46,43,27,57,41,45,21,70] mergeSort(nlist) print(nlist)
Post a Comment
Read more

Quick Sort In Python

# Python program for implementation of Quicksort Sort # This function takes last element as pivot, places # the pivot element at its correct position in sorted # array, and places all smaller (smaller than pivot) # to left of pivot and all greater elements to right # of pivot def partition(arr, low, high):     i = (low - 1)  # index of smaller element     pivot = arr[high]  # pivot     for j in range(low, high):         # If current element is smaller than or         # equal to pivot         if arr[j] <= pivot:             # increment index of smaller element             i = i + 1             arr[i], arr[j] = arr[j], arr[i]     arr[i + 1], arr[high] = arr[high], arr[i + 1]     return (i + 1) # The main function that implements QuickSort # arr[] --> Array to be sorted, # low --> Starting index, # high --> Ending index # Function to do Quick sort def quickSort(arr, low, high):     if low < high:         # pi
Post a Comment
Read more

Heap Sort in Python

# Python program for implementation of heap Sort # To heapify subtree rooted at index i. # n is size of heap def heapify(arr, n, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # See if left child of root exists and is # greater than root if l < n and arr[i] < arr[l]: largest = l # See if right child of root exists and is # greater than root if r < n and arr[largest] < arr[r]: largest = r # Change root, if needed if largest != i: arr[i],arr[largest] = arr[largest],arr[i] # swap # Heapify the root. heapify(arr, n, largest) # The main function to sort an array of given size def heapSort(arr): n = len(arr) # Build a maxheap. for i in range(n, -1, -1): heapify(arr, n, i) # One by one extract elements for i in range(n-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # swap heapify(arr, i, 0) # Driver code to test above arr = [ 12, 11, 13, 5, 6, 7] h
Post a Comment
Read more

Selection Sort in Python

def selection_sort(lst):     for i in range(len(lst)-1):         min = i         for j in range(i,len(lst)):             if(lst[j]<lst[min]):                 min = j         lst[min],lst[i]=lst[i],lst[min]     print(lst) lst = [90,65,12,98,31,20,89,71,90] selection_sort(lst)
Post a Comment
Read more

Google Drive Algo

Google Drive Link
Post a Comment
Read more