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[prims_algo.T, int], ...)

Module Contents

class graphs.minimum_spanning_tree_prims2.GraphUndirectedWeighted

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

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[prims_algo.T]) → tuple[dict[prims_algo.T, int], dict[prims_algo.T, prims_algo.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