Spanning Tree (Kruskal)

Finds the minimum/maximum spanning tree of an UNDIRECTED graph using Kruskal's Algorithm. This algorithm is more useful when dealing with sparse graphs.

Usage

spanning_tree_kruskal(graph: Graph, minimum: bool)

Parameters:
      graph : Graph
            Graph Object
      minimum : Boolean
            True for minimum, False for maximum

Returns:
      Graph
            Graph object of the spanning tree

Example

from jellybeans.algos import spanning_tree_kruskalfrom jellybeans.structures import Graphg = Graph()g.add_vertex(0)g.add_vertex(1)g.add_vertex(2)g.add_vertex(3)g.add_vertex(4)g.add_bidirected_edge(0, 1, (4, 4))g.add_bidirected_edge(0, 2, (4, 4))g.add_bidirected_edge(0, 3, (6, 6))g.add_bidirected_edge(0, 4, (6, 6))g.add_bidirected_edge(1, 2, (2, 2))g.add_bidirected_edge(2, 3, (8, 8))g.add_bidirected_edge(3, 4, (9, 9))res = spanning_tree_kruskal(g, 0, False)print(res.to_adj_list()) # {0: [(3, 6), (1, 4)], 1: [(0, 4)], 2: [(3, 8)], 3: [(4, 9), (2, 8), (0, 6)], 4: [(3, 9)]}