Spanning Tree (Prims)

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

Usage

spanning_tree_prim(graph: Graph, source: int, minimum: bool)

Parameters:
      graph : Graph
            Graph Object
      source : int
            Source Vertex
      minimum : Boolean
            True for minimum, False for maximum

Returns:
      Graph
            Graph object of the spanning tree

Example

from jellybeans.algos import spanning_tree_primfrom 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_prim(g, 0, False)print(res.to_adj_list()) # {0: [(4, 6), (1, 4)], 1: [(0, 4)], 2: [(3, 8)], 3: [(4, 9), (2, 8)], 4: [(0, 6), (3, 9)]}