graphs.minimum_spanning_tree_kruskal2

Attributes

T

Classes

DisjointSetTree
DisjointSetTreeNode
GraphUndirectedWeighted

Module Contents

class graphs.minimum_spanning_tree_kruskal2.DisjointSetTree

Bases: Generic[T]

find_set(data: T) → DisjointSetTreeNode[T]

link(node1: DisjointSetTreeNode[T], node2: DisjointSetTreeNode[T]) → None

make_set(data: T) → None

union(data1: T, data2: T) → None

map: dict[T, DisjointSetTreeNode[T]]

class graphs.minimum_spanning_tree_kruskal2.DisjointSetTreeNode(data: T)

Bases: Generic[T]

data

parent

rank = 0

class graphs.minimum_spanning_tree_kruskal2.GraphUndirectedWeighted

Bases: Generic[T]

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

add_node(node: T) → None

kruskal() → GraphUndirectedWeighted[T]

Details: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

Example: >>> g1 = GraphUndirectedWeighted[int]() >>> g1.add_edge(1, 2, 1) >>> g1.add_edge(2, 3, 2) >>> g1.add_edge(3, 4, 1) >>> g1.add_edge(3, 5, 100) # Removed in MST >>> g1.add_edge(4, 5, 5) >>> assert 5 in g1.connections[3] >>> mst = g1.kruskal() >>> assert 5 not in mst.connections[3]

>>> g2 = GraphUndirectedWeighted[str]()
>>> g2.add_edge('A', 'B', 1)
>>> g2.add_edge('B', 'C', 2)
>>> g2.add_edge('C', 'D', 1)
>>> g2.add_edge('C', 'E', 100) # Removed in MST
>>> g2.add_edge('D', 'E', 5)
>>> assert 'E' in g2.connections["C"]
>>> mst = g2.kruskal()
>>> assert 'E' not in mst.connections['C']

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

graphs.minimum_spanning_tree_kruskal2.T