bfs algorithm

def bfs(graph, start, end): queue = [] visited = [] path = [] queue.append(start) while queue: node = queue.pop(0) if node not in visited: visited.append(node) path.append(node) if node == end: return path queue.extend(graph[node]) return path

graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': [] } start = 'A' end = 'F' path = bfs(graph, start, end) print(path)

dfs algorithm

def dfs(graph, start, end): stack = [] visited = [] path = [] stack.append(start) while stack: node = stack.pop() if node not in visited: visited.append(node) path.append(node) if node == end: return path stack.extend(graph[node]) return path

graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': [] } start = 'A' end = 'F' path = dfs(graph, start, end) print(path)

bucket sort algorithm

def bucket_sort(arr): bucket = [] for i in range(len(arr)): bucket.append([]) for j in arr: index_b = int(10 * j) bucket[index_b].append(j) for i in range(len(arr)): bucket[i] = sorted(bucket[i]) k = 0 for i in range(len(arr)): for j in range(len(bucket[i])): arr[k] = bucket[i][j] k += 1 return arr

arr = [.42, .32, .33, .52, .37, .47, .51] print(bucket_sort(arr))

counting sort algorithm

def counting_sort(arr): max_element = int(max(arr)) min_element = int(min(arr)) range_of_elements = max_element - min_element + 1 count_arr = [0 for _ in range(range_of_elements)] output_arr = [0 for _ in range(len(arr))] for i in range(0, len(arr)): count_arr[arr[i] - min_element] += 1 for i in range(1, len(count_arr)): count_arr[i] += count_arr[i - 1] for i in range(len(arr) - 1, -1, -1): output_arr[count_arr[arr[i] - min_element] - 1] = arr[i] count_arr[arr[i] - min_element] -= 1 for i in range(0, len(arr)): arr[i] = output_arr[i] return arr

arr = [4, 2, 2, 8, 3, 3, 1] print(counting_sort(arr))

radix sort algorithm

def counting_sort(arr, exp1): n = len(arr) output = [0] (n) count = [0] (10) for i in range(0, n): index = (arr[i] / exp1) count[int(index % 10)] += 1 for i in range(1, 10): count[i] += count[i - 1] i = n - 1 while i >= 0: index = (arr[i] / exp1) output[count[int(index % 10)] - 1] = arr[i] count[int(index % 10)] -= 1 i -= 1 i = 0 for i in range(0, len(arr)): arr[i] = output[i]

def radix_sort(arr): max1 = max(arr) exp = 1 while max1 / exp > 0: counting_sort(arr, exp) exp *= 10

arr = [170, 45, 75, 90, 802, 24, 2, 66] radix_sort(arr) print(arr)

heap sort algorithm

def heapify(arr, n, i): largest = i l = 2 i + 1 r = 2 i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)

def heap_sort(arr): n = len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[i], arr[0] = arr[0], arr[i] heapify(arr, i, 0)

arr = [12, 11, 13, 5, 6, 7] heap_sort(arr) print(arr)

merge sort algorithm

def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 L = arr[:mid] R = arr[mid:] merge_sort(L) merge_sort(R) i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i < len(L): arr[k] = L[i] i += 1 k += 1 while j < len(R): arr[k] = R[j] j += 1 k += 1

arr = [12, 11, 13, 5, 6, 7] merge_sort(arr) print(arr)

quick sort algorithm

def partition(arr, low, high): i = (low - 1) pivot = arr[high] for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return (i + 1)

def quick_sort(arr, low, high): if low < high: pi = partition(arr, low, high) quick_sort(arr, low, pi - 1) quick_sort(arr, pi + 1, high)

arr = [10, 7, 8, 9, 1, 5] n = len(arr) quick_sort(arr, 0, n - 1) print(arr)

selection sort algorithm

def selection_sort(arr): for i in range(len(arr)): min_idx = i for j in range(i + 1, len(arr)): if arr[min_idx] > arr[j]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i]

arr = [64, 25, 12, 22, 11] selection_sort(arr) print(arr)

insertion sort algorithm

def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key

arr = [12, 11, 13, 5, 6] insertion_sort(arr) print(arr)

bubble sort algorithm

def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j]

arr = [64, 34, 25, 12, 22, 11, 90] bubble_sort(arr) print(arr)

prims algorithm without imports

def prims(graph): visited = [] path = [] visited.append(list(graph.keys())[0]) while len(visited) != len(graph): min = 999 for i in visited: for j in graph[i]: if j[1] < min and j[0] not in visited: min = j[1] node = j[0] parent = i path.append([parent, node, min]) visited.append(node) return path

graph = { 'A': [['B', 2], ['C', 3]], 'B': [['A', 2], ['C', 1], ['D', 1], ['E', 4]], 'C': [['A', 3], ['B', 1], ['F', 5]], 'D': [['B', 1], ['E', 1]], 'E': [['B', 4], ['D', 1], ['F', 1]], 'F': [['C', 5], ['E', 1]] } path = prims(graph) print(path)

kruskals algorithm without imports

class KruskalMST: def __init__(self, num_vertices): self.num_vertices = num_vertices self.edges = []

def add_edge(self, u, v, weight):
    self.edges.append((weight, u, v))

def kruskal(self):
    self.edges.sort()
    mst = []
    parent = list(range(self.num_vertices))

    def find(node):
        if parent[node] == node:
            return node
        parent[node] = find(parent[node])
        return parent[node]

    def union(u, v):
        root_u = find(u)
        root_v = find(v)
        parent[root_u] = root_v

    for weight, u, v in self.edges:
        if find(u) != find(v):
            mst.append((u, v, weight))
            union(u, v)

    return mst

Example Usage:

num_vertices = 4 kruskal_mst = KruskalMST(num_vertices) kruskal_mst.add_edge(0, 1, 4) kruskal_mst.add_edge(0, 2, 1) kruskal_mst.add_edge(1, 2, 2) kruskal_mst.add_edge(1, 3, 5) kruskal_mst.add_edge(2, 3, 3)

minimum_spanning_tree = kruskal_mst.kruskal() print(minimum_spanning_tree)

dijkstras algorithm without imports

def dijkstra(graph, src): dist = [999] len(graph) dist[src] = 0 sptSet = [False] len(graph) for cout in range(len(graph)): u = minDistance(dist, sptSet) sptSet[u] = True for v in range(len(graph)): if graph[u][v] > 0 and sptSet[v] == False and dist[v] > dist[u] + graph[u][v]: dist[v] = dist[u] + graph[u][v] return dist

def minDistance(dist, sptSet): min = 999 for v in range(len(graph)): if dist[v] < min and sptSet[v] == False: min = dist[v] min_index = v return min_index

graph = [ [0, 4, 0, 0, 0, 0, 0, 8, 0], [4, 0, 8, 0, 0, 0, 0, 11, 0], [0, 8, 0, 7, 0, 4, 0, 0, 2], [0, 0, 7, 0, 9, 14, 0, 0, 0], [0, 0, 0, 9, 0, 10, 0, 0, 0], [0, 0, 4, 14, 10, 0, 2, 0, 0], [0, 0, 0, 0, 0, 2, 0, 1, 6], [8, 11, 0, 0, 0, 0, 1, 0, 7], [0, 0, 2, 0, 0, 0, 6, 7, 0] ] dist = dijkstra(graph, 0) print(dist)

floyd warshall algorithm without imports

def floyd_warshall(graph): dist = graph for k in range(len(graph)): for i in range(len(graph)): for j in range(len(graph)): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) return dist

graph = [ [0, 5, 999, 10], [999, 0, 3, 999], [999, 999, 0, 1], [999, 999, 999, 0] ] dist = floyd_warshall(graph) print(dist)

bellman ford algorithm without imports

def bellman_ford(graph, src): dist = [999] * len(graph) dist[src] = 0 for i in range(len(graph) - 1): for u, v, w in graph: if dist[u] != 999 and dist[u] + w < dist[v]: dist[v] = dist[u] + w for u, v, w in graph: if dist[u] != 999 and dist[u] + w < dist[v]: print("Graph contains negative weight cycle") return return dist

graph = [ [0, 1, -1], [0, 2, 4], [1, 2, 3], [1, 3, 2], [1, 4, 2], [3, 2, 5], [3, 1, 1], [4, 3, -3] ] dist = bellman_ford(graph, 0) print(dist)

topological sort algorithm without imports

def topological_sort(graph): visited = [] stack = [] for i in range(len(graph)): if i not in visited: topological_sort_util(graph, i, visited, stack) return stack[::-1]

def topological_sort_util(graph, node, visited, stack): visited.append(node) for i in graph[node]: if i not in visited: topological_sort_util(graph, i, visited, stack) stack.append(node)

graph = { 0: [1, 2], 1: [2], 2: [], 3: [0, 2], 4: [0, 1] } stack = topological_sort(graph) print(stack)

boruvkas algorithm without imports

def boruvkas(graph): parent = [] cheapest = [] for node in range(len(graph)): parent.append(node) cheapest.append(-1) numTrees = len(graph) MSTweight = 0 while numTrees > 1: for node in range(len(graph)): cheapest[node] = -1 for node in range(len(graph)): for i in graph[node]: root = find(parent, node) dest = find(parent, i[0]) if root != dest: if cheapest[root] == -1 or cheapest[root][1] > i[1]: cheapest[root] = i for node in range(len(graph)): if cheapest[node] != -1: root1 = find(parent, cheapest[node][0]) root2 = find(parent, node) if root1 != root2: MSTweight += cheapest[node][1] union(parent, root1, root2) print("Edge %d-%d with weight %d included in MST" % (cheapest[node][0], node, cheapest[node][1])) numTrees = numTrees - 1 print("Weight of MST is %d" % MSTweight)

def find(parent, node): if parent[node] == node: return node return find(parent, parent[node])

def union(parent, x, y): xroot = find(parent, x) yroot = find(parent, y) parent[xroot] = yroot

graph = [ [[1, 4], [7, 8]], [[0, 4], [2, 8], [7, 11]], [[1, 8], [3, 7], [5, 4], [8, 2]], [[2, 7], [4, 9], [5, 14]], [[3, 9], [5, 10]], [[2, 4], [3, 14], [4, 10], [6, 2]], [[5, 2], [7, 1], [8, 6]], [[0, 8], [1, 11], [6, 1], [8, 7]], [[2, 2], [6, 6], [7, 7]] ] boruvkas(graph)

coin change algorithm without imports

def coin_change(coins, amount): dp = [0] + [float('inf')] * amount for coin in coins: for i in range(coin, amount + 1): dp[i] = min(dp[i], dp[i - coin] + 1) return dp[-1] if dp[-1] != float('inf') else -1

coins = [1, 2, 5] amount = 11 print(coin_change(coins, amount))

task scheduler algorithm without imports

def task_scheduler(tasks, n): d = {} for i in tasks: if i in d: d[i] += 1 else: d[i] = 1 max_freq = max(d.values()) max_freq_tasks = [] for i in d: if d[i] == max_freq: max_freq_tasks.append(i) return max(len(tasks), (max_freq - 1) * (n + 1) + len(max_freq_tasks))

tasks = ["A", "A", "A", "B", "B", "B"] n = 2 print(task_scheduler(tasks, n))

hauffman coding algorithm without imports

Huffman Coding in python

string = 'BCAADDDCCACACAC'

Creating tree nodes

class NodeTree(object):

def __init__(self, left=None, right=None):
    self.left = left
    self.right = right

def children(self):
    return (self.left, self.right)

def nodes(self):
    return (self.left, self.right)

def __str__(self):
    return '%s_%s' % (self.left, self.right)

Main function implementing huffman coding

def huffman_code_tree(node, left=True, binString=''): if type(node) is str: return {node: binString} (l, r) = node.children() d = dict() d.update(huffman_code_tree(l, True, binString + '0')) d.update(huffman_code_tree(r, False, binString + '1')) return d

Calculating frequency

freq = {} for c in string: if c in freq: freq[c] += 1 else: freq[c] = 1

freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)

nodes = freq

while len(nodes) > 1: (key1, c1) = nodes[-1] (key2, c2) = nodes[-2] nodes = nodes[:-2] node = NodeTree(key1, key2) nodes.append((node, c1 + c2))

nodes = sorted(nodes, key=lambda x: x[1], reverse=True)

huffmanCode = huffman_code_tree(nodes[0][0])

print(' Char | Huffman code ') print('----------------------') for (char, frequency) in freq: print(' %-4r |%12s' % (char, huffmanCode[char]))

activity

def MaxActivities(arr, n): selected = [] Activity.sort(key=lambda x: x[1]) i = 0 selected.append(arr[i])

for j in range(1, n):
    if arr[j][0] >= arr[i][1]:
        selected.append(arr[j])
        i = j
return selected

if __name__ == '__main__': Activity = [[5, 9], [1, 2], [3, 4], [0, 6], [5, 7], [8, 9]] n = len(Activity) selected = MaxActivities(Activity, n) print("Following activities are selected :") print(selected[0], end=""); for i in range(1, len(selected)): print(",", end=" ") print(selected[i], end=" ")