The Minimum Spanning Tree - Prim's Algorithm In Python
Written by Mike James
Thursday, 05 October 2023
Article Index
The Minimum Spanning Tree - Prim's Algorithm In Python
Prim's Algorithm In Python
Implementing Prim's algorithm
Listing

## Listing

The complete listing is:

`import tkinterimport randomimport mathimport random`
`size = 8height = 550width = 600`
`class Point:    X = 0    Y = 0`
`Pos = []Network = []`
`def distance(a, b):    return math.sqrt((a.X - b.X) ** 2 + (a.Y - b.Y) ** 2)`
`def showNetwork(canvas, Network):    canvas.delete("all")    for i in range(size):        p1 = Pos[i]        for j in range(i):            if Network[i][j] > 1:                p2 = Pos[j]                canvas.create_line(p1.X, p1.Y,                                          p2.X, p2.Y)    for i in range(size):        p1 = Pos[i]        canvas.create_rectangle(p1.X-5, p1.Y-5, p1.X+5,                                p1.Y+5, outline="black",                                 fill="red", width=2)`
`def setnet(canvas):    global Network    global Pos    Pos = [0 for j in range(size)]    Network = [[0 for j in range(size)]                              for i in range(size)]    maxlength = math.floor(        min(canvas.winfo_width(),                      canvas.winfo_height()) * 0.9)    minlength = math.floor(maxlength / size)    for i in range(size):        p = Point()        p.X = random.randint(minlength, maxlength)        p.Y = random.randint(minlength, maxlength)        Pos[i] = p        for j in range(i+1):            Network[i][j] = distance(Pos[i], Pos[j])            Network[j][i] = Network[i][j]    showNetwork(canvas, Network)`
`def closest(n, included, excluded):    smallest = -1    for i in range(n):        for j in range(size):            if excluded[j] == -1:                continue            if smallest == -1:                smallest = Network[included[i]]                                       [excluded[j]]            if Network[included[i]][excluded[j]] >                                              smallest:                continue            smallest = Network[included[i]][excluded[j]]            start = i            finish = j    return start, finish`
`def prims():    finished = [[0 for j in range(size)]                                 for i in range(size)]    included = [-1 for i in range(size)]    excluded = [i for i in range(size)]    included[0] = excluded[random.randint(0, size-1)]    excluded[included[0]] = -1    for n in range(1, size):        start, finish = closest(n, included, excluded)        included[n] = excluded[finish]        excluded[finish] = -1        finished[included[n]][included[start]] =                    Network[included[n]][included[start]]        finished[included[start]][included[n]] =                    Network[included[start]][included[n]]        showNetwork(C, finished)top = tkinter.Tk()C = tkinter.Canvas(top, bg="blue",                            height=height, width=width)button = tkinter.Button(top, text="Generate Network",                        command=lambda: setnet(C))`
`button.place(x=10, y=height-40)button = tkinter.Button(top, text="MST", command=prims)button.place(x=200, y=height-40)C.pack()top.mainloop()`

#### Related Articles:

Shortest Path Breakthrough

•  Mike James is the author of the Programmer's Python: Something Completely Different series of books which set out to show how Python diverges from other programming languages and how its special features deserve our attention.

 AWS Low Cost Mailing List Using phpList And SESRunning a mailing list is not easy or cheap, but if you use AWS it can be. Find out how to create a low-cost and highly effective mailing list server. + Full Project Setting Up Site-To-Site OpenVPN Setting up a point-to-point VPN is relatively easy but site-to-site is much more complicated involving certificates and more IP addresses than you can count. Find out how to do it using OpenVPN. + Full Project Other Projects

 Pharo 12 Adds New Breakpoint System09/05/2024The latest version of Pharo, the open-source Smalltalk-inspired language and core library adds a new breakpoint model based on the debug point system. + Full Story Amazon Bedrock Adds Support For Anthropic's Claude3 Opus14/05/2024Bedrock, Amazon's fully managed service for building generative AI applications, has been enhanced with support for Anthropic's Claude 3 Opus Foundation Model. + Full Story More News