graphs.minimum_spanning_tree_prims2

Prim’s (also known as Jarník’s) algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Attributes

T

Classes

GraphUndirectedWeighted	Graph Undirected Weighted Class
MinPriorityQueue	Minimum Priority Queue Class

Functions

get_child_left_position(→ int)	heap helper function get the position of the left child of the current node
get_child_right_position(→ int)	heap helper function get the position of the right child of the current node
get_parent_position(→ int)	heap helper function get the position of the parent of the current node
prims_algo(→ tuple[dict[T, int], dict[T, T | None]])

Module Contents

class graphs.minimum_spanning_tree_prims2.GraphUndirectedWeighted

Bases: Generic[T]

Graph Undirected Weighted Class

Functions: add_node: function to add a node in the graph add_edge: function to add an edge between 2 nodes in the graph

__len__() → int

__repr__() → str

add_edge(node1: T, node2: T, weight: int) → None

add_node(node: T) → None

connections: dict[T, dict[T, int]]

nodes: int = 0

class graphs.minimum_spanning_tree_prims2.MinPriorityQueue

Bases: Generic[T]

Minimum Priority Queue Class

Functions: is_empty: function to check if the priority queue is empty push: function to add an element with given priority to the queue extract_min: function to remove and return the element with lowest weight (highest

priority)

update_key: function to update the weight of the given key _bubble_up: helper function to place a node at the proper position (upward

movement)

_bubble_down: helper function to place a node at the proper position (downward

movement)

_swap_nodes: helper function to swap the nodes at the given positions

>>> queue = MinPriorityQueue()

>>> queue.push(1, 1000)
>>> queue.push(2, 100)
>>> queue.push(3, 4000)
>>> queue.push(4, 3000)

>>> queue.extract_min()
2

>>> queue.update_key(4, 50)

>>> queue.extract_min()
4
>>> queue.extract_min()
1
>>> queue.extract_min()
3

__len__() → int

__repr__() → str

_bubble_down(elem: T) → None

_bubble_up(elem: T) → None

_swap_nodes(node1_pos: int, node2_pos: int) → None

extract_min() → T

is_empty() → bool

push(elem: T, weight: int) → None

update_key(elem: T, weight: int) → None

elements: int = 0

heap: list[tuple[T, int]] = []

position_map: dict[T, int]

graphs.minimum_spanning_tree_prims2.get_child_left_position(position: int) → int

heap helper function get the position of the left child of the current node

>>> get_child_left_position(0)
1

graphs.minimum_spanning_tree_prims2.get_child_right_position(position: int) → int

heap helper function get the position of the right child of the current node

>>> get_child_right_position(0)
2

graphs.minimum_spanning_tree_prims2.get_parent_position(position: int) → int

heap helper function get the position of the parent of the current node

>>> get_parent_position(1)
0
>>> get_parent_position(2)
0

graphs.minimum_spanning_tree_prims2.prims_algo(graph: GraphUndirectedWeighted[T]) → tuple[dict[T, int], dict[T, T | None]]

>>> graph = GraphUndirectedWeighted()

>>> graph.add_edge("a", "b", 3)
>>> graph.add_edge("b", "c", 10)
>>> graph.add_edge("c", "d", 5)
>>> graph.add_edge("a", "c", 15)
>>> graph.add_edge("b", "d", 100)

>>> dist, parent = prims_algo(graph)

>>> abs(dist["a"] - dist["b"])
3
>>> abs(dist["d"] - dist["b"])
15
>>> abs(dist["a"] - dist["c"])
13

graphs.minimum_spanning_tree_prims2.T