graphs.prim

Prim’s Algorithm.

Determines the minimum spanning tree(MST) of a graph using the Prim’s Algorithm.

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

Classes

Vertex

Class Vertex.

Functions

connect(graph, a, b, edge)
prim(→ list)	Prim's Algorithm.
prim_heap(→ collections.abc.Iterator[tuple])	Prim's Algorithm with min heap.
test_vector(→ None)	# Creates a list to store x vertices.

Module Contents

class graphs.prim.Vertex(id_)

Class Vertex.

__lt__(other)

Comparison rule to < operator.

__repr__()

Return the vertex id.

add_edge(vertex, weight)

Destination vertex and weight.

add_neighbor(vertex)

Add a pointer to a vertex at neighbor’s list.

edges

id

key = None

neighbors = []

pi = None

graphs.prim.connect(graph, a, b, edge)

graphs.prim.prim(graph: list, root: Vertex) → list

Prim’s Algorithm.

Runtime:

O(mn) with m edges and n vertices

Return:

List with the edges of a Minimum Spanning Tree

Usage:

prim(graph, graph[0])

graphs.prim.prim_heap(graph: list, root: Vertex) → collections.abc.Iterator[tuple]

Prim’s Algorithm with min heap.

Runtime:

O((m + n)log n) with m edges and n vertices

Yield:

Edges of a Minimum Spanning Tree

Usage:

prim(graph, graph[0])

graphs.prim.test_vector() → None

# Creates a list to store x vertices. >>> x = 5 >>> G = [Vertex(n) for n in range(x)]

>>> connect(G, 1, 2, 15)
>>> connect(G, 1, 3, 12)
>>> connect(G, 2, 4, 13)
>>> connect(G, 2, 5, 5)
>>> connect(G, 3, 2, 6)
>>> connect(G, 3, 4, 6)
>>> connect(G, 0, 0, 0)  # Generate the minimum spanning tree:
>>> G_heap = G[:]
>>> MST = prim(G, G[0])
>>> MST_heap = prim_heap(G, G[0])
>>> for i in MST:
...     print(i)
(2, 3)
(3, 1)
(4, 3)
(5, 2)
>>> for i in MST_heap:
...     print(i)
(2, 3)
(3, 1)
(4, 3)
(5, 2)