write me a Kruskal algorithm python program
- User
write me a Kruskal algorithm python program
- Assistant
Sure, here is a sample implementation of 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]) def find(self, parent, i): if parent[i] == i: return i return self.find(parent, parent[i]) def 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 def kruskal(self): result = [] i = 0 e = 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.union(parent, rank, x, y) return resultTo use this program, you can create a Graph object and add edges like this:
g = Graph(4) g.add_edge(0, 1, 10) g.add_edge(0, 2, 6) g.add_edge(0, 3, 5) g.add_edge(1, 3, 15) g.add_edge(2, 3, 4) print(g.kruskal())This will produce the output:
[[2, 3, 4], [0, 3, 5], [0, 1, 10]] - User
write me Prim’s algorithm python program
- Assistant
Sure, here is a sample implementation of Prim's algorithm in Python:
import sys class Graph: def __init__(self, vertices): self.V = vertices self.graph = [[0 for column in range(vertices)] for row in range(vertices)] def get_min_key(self, key, mst_set): min_key = sys.maxsize min_index = -1 for v in range(self.V): if key[v] < min_key and mst_set[v] == False: min_key = key[v] min_index = v return min_index def prim(self): key = [sys.maxsize] * self.V parent = [None] * self.V key[0] = 0 mst_set = [False] * self.V parent[0] = -1 for cout in range(self.V): u = self.get_min_key(key, mst_set) mst_set[u] = True for v in range(self.V): if self.graph[u][v] > 0 and mst_set[v] == False and key[v] > self.graph[u][v]: key[v] = self.graph[u][v] parent[v] = u mst = [] for i in range(1, self.V): mst.append([parent[i], i, self.graph[i][parent[i]]]) return mstTo use this program, you can create a Graph object and add edges like this:
g = Graph(5) g.graph = [[0, 2, 0, 6, 0], [2, 0, 3, 8, 5], [0, 3, 0, 0, 7], [6, 8, 0, 0, 9], [0, 5, 7, 9, 0]] print(g.prim())This will produce the output:
[[0, 1, 2], [1, 2, 3], [0, 3, 6], [1, 4, 5]] - User
write me Binary tree traversal python program
- Assistant
Sure, here's a sample implementation of a binary tree traversal program in Python:
class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None def inorder_traversal(node): if node: inorder_traversal(node.left) print(node.data, end=" ") inorder_traversal(node.right) def preorder_traversal(node): if node: print(node.data, end=" ") preorder_traversal(node.left) preorder_traversal(node.right) def postorder_traversal(node): if node: postorder_traversal(node.left) postorder_traversal(node.right) print(node.data, end=" ") # Example tree # 1 # / \ # 2 3 # \ / \ # 4 5 6 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.right = TreeNode(4) root.right.left = TreeNode(5) root.right.right = TreeNode(6) print("Inorder Traversal:", end=" ") inorder_traversal(root) print() print("Preorder Traversal:", end=" ") preorder_traversal(root) print() print("Postorder Traversal:", end=" ") postorder_traversal(root) print()This program defines a
TreeNodeclass to represent each node in the binary tree, and three traversal functions:inorder_traversal: traverses the tree in left-root-right orderpreorder_traversal: traverses the tree in root-left-right orderpostorder_traversal: traverses the tree in left-right-root order
You can create a binary tree with the
TreeNodeclass, and then call any of the traversal functions to traverse the tree. The above example prints out:Inorder Traversal: 2 4 1 5 3 6 Preorder Traversal: 1 2 4 3 5 6 Postorder Traversal: 4 2 5 6 3 1 - User
write a Height-balanced binary search tree python program
- Assistant
Sure, here is an implementation of a Height-balanced binary search tree (AVL Tree) in Python:
class Node: def __init__(self, val): self.val = val self.left = None self.right = None self.height = 1 class AVLTree: def __init__(self): self.root = None def insert(self, root, val): if not root: return Node(val) elif val < root.val: root.left = self.insert(root.left, val) else: root.right = self.insert(root.right, val) root.height = 1 + max(self.get_height(root.left), self.get_height(root.right)) balance = self.get_balance(root) if balance > 1 and val < root.left.val: return self.right_rotate(root) if balance < -1 and val > root.right.val: return self.left_rotate(root) if balance > 1 and val > root.left.val: root.left = self.left_rotate(root.left) return self.right_rotate(root) if balance < -1 and val < root.right.val: root.right = self.right_rotate(root.right) return self.left_rotate(root) return root def left_rotate(self, node): right_child = node.right left_of_right_child = right_child.left right_child.left = node node.right = left_of_right_child node.height = 1 + max(self.get_height(node.left), self.get_height(node.right)) right_child.height = 1 + max(self.get_height(right_child.left), self.get_height(right_child.right)) return right_child def right_rotate(self, node): left_child = node.left right_of_left_child = left_child.right left_child.right = node node.left = right_of_left_child node.height = 1 + max(self.get_height(node.left), self.get_height(node.right)) left_child.height = 1 + max(self.get_height(left_child.left), self.get_height(left_child.right)) return left_child def get_height(self, node): if not node: return 0 return node.height def get_balance(self, node): if not node: return 0 return self.get_height(node.left) - self.get_height(node.right) def inorder(self, node): if node: self.inorder(node.left) print(node.val, end=' ') self.inorder(node.right) def preorder(self, node): if node: print(node.val, end=' ') self.preorder(node.left) self.preorder(node.right) avl = AVLTree() root = None root = avl.insert(root, 10) root = avl.insert(root, 20) root = avl.insert(root, 30) root = avl.insert(root, 40) root = avl.insert(root, 50) root = avl.insert(root, 25) print("Preorder Traversal after insertion:") avl.preorder(root) print()In this implementation, we have a
Nodeclass and anAVLTreeclass. TheAVLTreeclass has aninsert()method that does the work of inserting new nodes into the tree, rebalancing the tree as necessary. TheAVLTreeclass also has aleft_rotate()method and aright_rotate()method for rebalancing the tree. Finally, there areinorder()andpreorder()traversal methods for printing out the tree.To use this program, initialize an
AVLTreeobject, create a root node, and then call theinsert()method to add nodes into the tree. After insertion, you can use thepreorder()method to print out the tree in preorder traversal.The above example outputs:
Preorder Traversal after insertion: 30 20 10 25 40 50 - User
write a B-trees python program
- Assistant
Sure, here's an implementation of a B-tree in Python:
class Node: def __init__(self, leaf=False): self.keys = [] self.children = [] self.leaf = leaf def __str__(self): return str(self.keys) class BTree: def __init__(self, t): self.root = Node(leaf=True) self.t = t def search(self, k, x=None): if isinstance(x, Node): i = 0 while i < len(x.keys) and k > x.keys[i]: i += 1 if i < len(x.keys) and k == x.keys[i]: return (x, i) elif x.leaf: return None else: return self.search(k, x.children[i]) else: return self.search(k, self.root) def insert(self, k): r = self.root if len(r.keys) == (2*self.t) - 1: s = Node() self.root = s s.children.insert(0, r) self._split_child(s, 0) self._insert_nonfull(s, k) else: self._insert_nonfull(r, k) def _insert_nonfull(self, x, k): i = len(x.keys) - 1 if x.leaf: x.keys.append(0) while i >= 0 and k < x.keys[i]: x.keys[i+1] = x.keys[i] i -= 1 x.keys[i+1] = k else: while i >= 0 and k < x.keys[i]: i -= 1 i += 1 if len(x.children[i].keys) == (2*self.t) - 1: self._split_child(x, i) if k > x.keys[i]: i += 1 self._insert_nonfull(x.children[i], k) def _split_child(self, x, i): t = self.t y = x.children[i] z = Node(leaf=y.leaf) x.children.insert(i+1, z) x.keys.insert(i, y.keys[t-1]) z.keys = y.keys[t:(2*t - 1)] y.keys = y.keys[0:(t-1)] if not y.leaf: z.children = y.children[t:(2*t)] y.children = y.children[0:(t-1)] def delete(self, k): (n, i) = self.search(k) if n is not None: if n.leaf: del n.keys[i] self._rebalance(n) else: pred = self._get_predecessor(n, i) n.keys[i] = pred if len(n.children[i].keys) < self.t: self._fill_child(n, i) else: return None def _get_predecessor(self, x, i): cur = x.children[i] while not cur.leaf: cur = cur.children[-1] return cur.keys[-1] def _fill_child(self, x, i): if i > 0 and len(x.children[i-1].keys) > self.t - 1: self._move_right(x, i) elif i < len(x.children) - 1 and len(x.children[i+1].keys) > self.t - 1: self._move_left(x, i) else: if i == len(x.children) - 1: i = i - 1 self._merge(x, i) def _move_right(self, x, i): child = x.children[i] sibling = x.children[i-1] child.keys.insert(0, x.keys[i-1]) x.keys[i-1] = sibling.keys.pop() if not child.leaf: child.children.insert(0, sibling.children.pop()) def _move_left(self, x, i): child = x.children[i] sibling = x.children[i+1] child.keys.append(x.keys[i]) x.keys[i] = sibling.keys.pop(0) if not child.leaf: child.children.append(sibling.children.pop(0)) def _merge(self, x, i): child = x.children[i] sibling = x.children[i+1] child.keys.append(x.keys.pop(i)) child.keys += sibling.keys if not child.leaf: child.children += sibling.children x.children.pop(i+1) if len(x.keys) == 0: self.root = child def _rebalance(self, x): if len(x.keys) < self.t - 1: if x == self.root: if not x.keys: self.root = x.children[0] del x return elif self._should_merge(x): parent, i = self._get_parent(x) if i == 0: self._merge_right_sibling(parent, i) else: self._merge_left_sibling(parent, i) self._rebalance(parent) elif self._should_borrow(x): parent, i = self._get_parent(x) if i != 0 and len(parent.children[i-1].keys) > self.t - 1: self._borrow_from_left_sibling(x, parent, i) elif i != len(parent.children) - 1 and len(parent.children[i+1].keys) > self.t - 1: self._borrow_from_right_sibling(x, parent, i) else: if i == len(parent.children) - 1: i = i - 1 self._merge(x.parent, i) self._rebalance(parent) def _should_borrow(self, x): return len(x.keys) > self.t - 2 def _should_merge(self, x): return len(x.keys) == self.t - 2 def _get_parent(self, x): parent = None i = None if x != self.root: for i, n in enumerate(x.parent.children): if n == x: parent = x.parent break return parent, i def _borrow_from_left_sibling(self, x, parent, i): child = parent.children[i] sibling = parent.children[i-1] x.keys.insert(0, parent.keys[i-1]) parent.keys[i-1] = sibling.keys.pop(-1) if not x.leaf: x.children.insert(0, sibling.children.pop(-1)) def _borrow_from_right_sibling(self, x, parent, i): child = parent.children[i] sibling = parent.children[i+1] x.keys.append(parent.keys[i]) parent.keys[i] = sibling.keys.pop(0) if not x.leaf: x.children.append(sibling.children.pop(0)) def _merge_right_sibling(self, parent, i): child = parent.children[i] sibling = parent.children[i+1] child.keys.append(parent.keys.pop(i)) child.keys += sibling.keys if not child.leaf: child.children += sibling.children parent.children.pop(i+1) def _merge_left_sibling(self, parent, i): child = parent.children[i] sibling = parent.children[i-1] sibling.keys.append(parent.keys.pop(i-1)) sibling.keys += child.keys if not child.leaf: sibling.children += child.children parent.children.pop(i) def __str__(self): s = [] q = [(self.root, 0)] while q: cur, level = q.pop(0) if cur.leaf: s.append((level, cur)) else: s.append((level, cur)) for c in cur.children: q.append((c, level+1)) prev_level = -1 out = "" for level, node in s: if level == prev_level: out += str(node.keys) + " " else: out += "\n" + str(node.keys) + " " prev_level = level return outIn this implementation, we have a
Nodeclass
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.