from collections import defaultdict class Graph: def __init__(self): self.graph = defaultdict(list)

def addedges(self, u, v ):
    self.graph[u].append(v)

def Depthfirstsearch(self,v, visited):
    visited.add(v)
    print(v, end=' ')
    for adjacent in self.graph[v]:
        if adjacent not in visited:
            self.Depthfirstsearch(adjacent, visited)

g = Graph() g.addedges(1, 5) g.addedges(2, 0) g.addedges(0, 3) g.addedges(2, 4) g.addedges(2, 3) g.addedges(3, 0) g.addedges(4, 5)

print("Depth first search from vertex 2") visited = set() g.Depthfirstsearch(2,visited)

def bfs(visitnext, graph, Currentnode): visitnext.append(Currentnode) queue = [] queue.append(Currentnode)

while queue:
    s = queue.pop(0)
    print(s)

    for adjacent in graph[s]:
        if adjacent not in visitnext:
            visitnext.append(adjacent)
            queue.append(adjacent)

graph = { 0: [1, 2, 3], 1: [0,1,2], 2: [2,3,5], 3: [1, 2], 5: [] } print("Breadth first search from vertex 1") bfs([], graph, 1)

class Node: def __init__(self, info): self.info = info self.left = None self.right = None self.level = None

def preOrder(root): if root == None: return print(root.info, end=" ") preOrder(root.left) preOrder(root.right)

class BinarySearchTree: def _init_(self): self.root = None

def insert(self, val):
    cur = self.root
    if not cur:
        self.root = Node(val)
        return self.root
    while cur:
        if cur.info > val:
            if cur.left:
                cur = cur.left
            else:
                cur.left = Node(val)
                break
        else:
            if cur.right:
                cur = cur.right
            else:
                cur.right = Node(val)
                break
    return self.root

tree = BinarySearchTree() t = int(input()) arr = list(map(int, input().split())) for i in range(t): tree.insert(arr[i]) preOrder(tree.root)

import sys

class MaxHeap:

def _init_(self, maxsize):

    self.maxsize = maxsize
    self.size = 0
    self.Heap = [0] * (self.maxsize + 1)
    self.Heap[0] = sys.maxsize
    self.FRONT = 1

# Function to return the position of
# parent for the node currently
# at pos
def parent(self, pos):

    return pos // 2

# Function to return the position of
# the left child for the node currently
# at pos
def leftChild(self, pos):

    return 2 * pos

# Function to return the position of
# the right child for the node currently
# at pos
def rightChild(self, pos):

    return (2 * pos) + 1

# Function that returns true if the passed
# node is a leaf node
def isLeaf(self, pos):

    if pos >= (self.size//2) and pos <= self.size:
        return True
    return False

# Function to swap two nodes of the heap
def swap(self, fpos, spos):

    self.Heap[fpos], self.Heap[spos] = (self.Heap[spos],
                                        self.Heap[fpos])

# Function to heapify the node at pos
def maxHeapify(self, pos):

    # If the node is a non-leaf node and smaller
    # than any of its child
    if not self.isLeaf(pos):
        if (self.Heap[pos] < self.Heap[self.leftChild(pos)] or
            self.Heap[pos] < self.Heap[self.rightChild(pos)]):

            # Swap with the left child and heapify
            # the left child
            if (self.Heap[self.leftChild(pos)] >
                self.Heap[self.rightChild(pos)]):
                self.swap(pos, self.leftChild(pos))
                self.maxHeapify(self.leftChild(pos))

            # Swap with the right child and heapify
            # the right child
            else:
                self.swap(pos, self.rightChild(pos))
                self.maxHeapify(self.rightChild(pos))

# Function to insert a node into the heap
def insert(self, element):

    if self.size >= self.maxsize:
        return
    self.size += 1
    self.Heap[self.size] = element

    current = self.size

    while (self.Heap[current] >
        self.Heap[self.parent(current)]):
        self.swap(current, self.parent(current))
        current = self.parent(current)

# Function to print the contents of the heap
def Print(self):

    for i in range(1, (self.size // 2) + 1):
        print(" PARENT : " + str(self.Heap[i]) +
            " LEFT CHILD : " + str(self.Heap[2 * i]) +
            " RIGHT CHILD : " + str(self.Heap[2 * i + 1]))

# Function to remove and return the maximum
# element from the heap
def extractMax(self):

    popped = self.Heap[self.FRONT]
    self.Heap[self.FRONT] = self.Heap[self.size]
    self.size -= 1
    self.maxHeapify(self.FRONT)

    return popped

Driver Code

if _name_ == "_main_":

print('The maxHeap is ')

maxHeap = MaxHeap(15)
maxHeap.insert(5)
maxHeap.insert(3)
maxHeap.insert(17)
maxHeap.insert(10)
maxHeap.insert(84)
maxHeap.insert(19)
maxHeap.insert(6)
maxHeap.insert(22)
maxHeap.insert(9)

maxHeap.Print()

print("The Max val is " + str(maxHeap.extractMax()))

heap sort////////////////////\

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 = 2i + 1 r = 2 i + 2 # right = 2i + 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.

Since last parent will be at ((n//2)-1) we can start at that location.

for i in range(n // 2 - 1, -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] heapSort(arr) n = len(arr) print ("Sorted array is") for i in range(n): print ("%d" %arr[i]),)

import sys

class MinHeap:

def _init_(self, maxsize):
    self.maxsize = maxsize
    self.size = 0
    self.Heap = [0]*(self.maxsize + 1)
    self.Heap[0] = -1 * sys.maxsize
    self.FRONT = 1

# Function to return the position of
# parent for the node currently
# at pos
def parent(self, pos):
    return pos//2

# Function to return the position of
# the left child for the node currently
# at pos
def leftChild(self, pos):
    return 2 * pos

# Function to return the position of
# the right child for the node currently
# at pos
def rightChild(self, pos):
    return (2 * pos) + 1

# Function that returns true if the passed
# node is a leaf node
def isLeaf(self, pos):
    return pos*2 > self.size

# Function to swap two nodes of the heap
def swap(self, fpos, spos):
    self.Heap[fpos], self.Heap[spos] = self.Heap[spos], self.Heap[fpos]

# Function to heapify the node at pos
def minHeapify(self, pos):

    # If the node is a non-leaf node and greater
    # than any of its child
    if not self.isLeaf(pos):
        if (self.Heap[pos] > self.Heap[self.leftChild(pos)] or
        self.Heap[pos] > self.Heap[self.rightChild(pos)]):

            # Swap with the left child and heapify
            # the left child
            if self.Heap[self.leftChild(pos)] < self.Heap[self.rightChild(pos)]:
                self.swap(pos, self.leftChild(pos))
                self.minHeapify(self.leftChild(pos))

            # Swap with the right child and heapify
            # the right child
            else:
                self.swap(pos, self.rightChild(pos))
                self.minHeapify(self.rightChild(pos))

# Function to insert a node into the heap
def insert(self, element):
    if self.size >= self.maxsize :
        return
    self.size+= 1
    self.Heap[self.size] = element

    current = self.size

    while self.Heap[current] < self.Heap[self.parent(current)]:
        self.swap(current, self.parent(current))
        current = self.parent(current)

# Function to print the contents of the heap
def Print(self):
    for i in range(1, (self.size//2)+1):
        print(" PARENT : "+ str(self.Heap[i])+" LEFT CHILD : "+
                            str(self.Heap[2 * i])+" RIGHT CHILD : "+
                            str(self.Heap[2 * i + 1]))

# Function to build the min heap using
# the minHeapify function
def minHeap(self):

    for pos in range(self.size//2, 0, -1):
        self.minHeapify(pos)

# Function to remove and return the minimum
# element from the heap
def remove(self):

    popped = self.Heap[self.FRONT]
    self.Heap[self.FRONT] = self.Heap[self.size]
    self.size-= 1
    self.minHeapify(self.FRONT)
    return popped

Driver Code

if _name_ == "_main_":

print('The minHeap is ')
minHeap = MinHeap(15)
minHeap.insert(5)
minHeap.insert(3)
minHeap.insert(17)
minHeap.insert(10)
minHeap.insert(84)
minHeap.insert(19)
minHeap.insert(6)
minHeap.insert(22)
minHeap.insert(9)
minHeap.minHeap()

minHeap.Print()
print("The Min val is " + str(minHeap.remove()))

global flag def findHeightHelp(root,x): global height if root is None: return -1 leftht=findHeightHelp(root.left,x) rightht=findHeightHelp(root.right,x) ans=max(leftht,rightht)+1 if root==x: height=ans return ans

class bst:

def _init_(self):
    self.s=0
    self.root=None

class node:

    def _init_(self,val):
        self.element=val
        self.left=None
        self.right=None

def insert(self,root,val):

    if root is None:
        self.root=self.node(val)
        self.s += 1
        return


    if root:

        if val < root.element:

            if root.left:
                self.insert(root.left,val)
            else:
                root.left=self.node(val)
                self.s += 1

        else:
                if root.right:
                    self.insert(root.right,val)
                else:
                    root.right = self.node(val)
                    self.s += 1

def buildtree(self,li):
    for i in range(len(li)):
        self.insert(self.root,li[i])

def preorder(self,root):
    if root:
        print(root.element,end=" ")
        self.preorder(root.left)
        self.preorder(root.right)

def postorder(self,root):
    if root:
        self.postorder(root.left)
        self.postorder(root.right)
        print(root.element,end=" ")

def size(self):
    print(self.s)

def findElement(self, root, val):
    global flag
    if root is None:
        flag=1
        return

    if root:
        if(root.element==val):
            flag=0
            return True
        else:
            if val < root.element:
                self.findElement(root.left, val)
            else:
                self.findElement(root.right, val)

def depth(self,root,val):

    if root:
        if root.element==val:
            return 0
        else:
            if val<root.element:
                return 1+self.depth(root.left,val)
            else:
                return 1+self.depth(root.right,val)

def isRoot(self,val):
    if val==self.root.element:
        print("True")
    else:
        print("False")

def getheight(self,val):
    global height
    findHeightHelp(self.root,val)
    return height

def printReverseInorder(self,root):
    if root is None:
        return
    if root:
        self.printReverseInorder(root.right)
        print(root.element,end=" ")
        self.printReverseInorder(root.left)

def printLevelOrder(self,root):
    if root is None:
        return -1
    que = []
    que.append(root)
    while len(que) > 0:
        print(que[0].element, end=" ")
        node = que.pop(0)
        if node.left is not None:
            que.append(node.left)
        if node.right is not None:
            que.append(node.right)
    print("")

def getChildren(self, root, val):
    if root.element == val:
        if root.left or root.right:
            if root.left:
                print(root.left.element, end=" ")
            if root.right:
                print(root.right.element, end=" ")
            print("")
            return
        else:
            print("False")
            return
    elif val < root.element:
        if root.left is not None:
            self.getChildren(root.left, val)
    elif val > root.element:
        if root.right is not None:
            self.getChildren(root.right, val)

def printLeaves(self, root):

    if root.left:
        self.printLeaves(root.left)
    if root.right:
        self.printLeaves(root.right)
    if root.right is None and root.left is None:
        print(root.element, end=" ")

def isInternal(self, root, val):
    if root.element == val:
        if root.left is None and root.right is None:
            print("False")
            return
        else:
            print("True")
            return
    else:
        if val < root.element:
            if root.left:
                self.isInternal(root.left,val)
        elif val > root.element:
            if root.right:
                self.isInternal(root.right,val)

def isExternal(self,root, val):
    if root.element == val:
        if root.left is None and root.right is None:
            print("True")
            return
        else:
            print("False")
            return
    else:
        if val < root.element:
            if root.left:
                self.isExternal(root.left,val)
        elif val > root.element:
            if root.right:
                self.isExternal(root.right,val)

def EulerTree(self,root,euler):
    euler.append(root.element)
    if root.left:
        euler = self.EulerTree(root.left, euler)
        euler.append(root.element)
    if root.right:
        euler = self.EulerTree(root.right, euler)
        euler.append(root.element)
    return euler

def printEulerTour(self,root):
    euler = []
    euler = self.EulerTree(root, euler)
    for i in range(len(euler)):
        print(euler[i], end=" ")

x=bst() sz=int(input()) num = list(map(int, input().split(" ")))

a=num.count(-1) for i in range(a): num.remove(-1) x.buildtree(num) n=int(input())

for j in range(n): str=[] str1 = input() str = str1.split() if len(str) > 1: str[1] = int(str[1]) if str[0] == "PLO": x.printLevelOrder(x.root) elif str[0] == "POST": x.postorder(x.root)

    elif str[0] == "P":
        x.preorder(x.root)

    elif str[0] == "SORT":
        tlist = num.copy()
        tlist.sort()
        for m in tlist:
            print(m,end=" ")
        print("")
    elif str[0] == "PL":
        x.printLeaves(x.root)
        print("")
    elif str[0] == "GH":
        print(x.getheight(x.root))
    elif str[0] == "S":
        x.size()
    elif str[0] == "PRI":
        x.printReverseInorder(x.root)
        print("")
    elif str[0] == "FE":
        x.findElement(x.root,str[1])
        if flag==0:
            print("Element Found",end=" ")
            print(x.depth(x.root,str[1]))
        if flag==1:
            print("Search Unsuccessful")
    elif str[0] == "IR":
        x.isRoot(str[1])
    elif str[0] == "GC":
        x.getChildren(x.root,str[1])
    elif str[0] == "II":
        x.isInternal(x.root,str[1])
    elif str[0] == "IE":
        x.isExternal(x.root,str[1])
    elif str[0] == "PET":
        x.printEulerTour(x.root)

Prim's Algorithm in Python

INF = 9999999

number of vertices in graph

V = 5

G = [[0, 9, 75, 0, 0], [9, 0, 95, 19, 42], [75, 95, 0, 51, 66], [0, 19, 51, 0, 31], [0, 42, 66, 31, 0]]

selected = [0, 0, 0, 0, 0]

no_edge = 0 selected[0] = True print("Edge : Weight\n") while (no_edge < V - 1):

minimum = INF
x = 0
y = 0
for i in range(V):
    if selected[i]:
        for j in range(V):
            if ((not selected[j]) and G[i][j]):  
                # not in selected and there is an edge
                if minimum > G[i][j]:
                    minimum = G[i][j]
                    x = i
                    y = j
print(str(x) + "-" + str(y) + ":" + str(G[x][y]))
selected[y] = True
no_edge += 1

Kruskal's algorithm in Python

class Graph: def __init__(self, vertices): self.V = vertices self.graph = []

def add_edge(self, u, v, w):
    self.graph.append([u, v, w])

# Search function

def find(self, parent, i):
    if parent[i] == i:
        return i
    return self.find(parent, parent[i])

def apply_union(self, parent, rank, x, y):
    xroot = self.find(parent, x)
    yroot = self.find(parent, y)
    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1

#  Applying Kruskal algorithm
def kruskal_algo(self):
    result = []
    i, e = 0, 0
    self.graph = sorted(self.graph, key=lambda item: item[2])
    parent = []
    rank = []
    for node in range(self.V):
        parent.append(node)
        rank.append(0)
    while e < self.V - 1:
        u, v, w = self.graph[i]
        i = i + 1
        x = self.find(parent, u)
        y = self.find(parent, v)
        if x != y:
            e = e + 1
            result.append([u, v, w])
            self.apply_union(parent, rank, x, y)
    for u, v, weight in result:
        print("%d - %d: %d" % (u, v, weight))

g = Graph(6) g.add_edge(0, 1, 4) g.add_edge(0, 2, 4) g.add_edge(1, 2, 2) g.add_edge(1, 0, 4) g.add_edge(2, 0, 4) g.add_edge(2, 1, 2) g.add_edge(2, 3, 3) g.add_edge(2, 5, 2) g.add_edge(2, 4, 4) g.add_edge(3, 2, 3) g.add_edge(3, 4, 3) g.add_edge(4, 2, 4) g.add_edge(4, 3, 3) g.add_edge(5, 2, 2) g.add_edge(5, 4, 3) g.kruskal_algo()