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 tkinter
import random
import math
import random
size = 8
height = 550
width = 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()

net1

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 SES

Running 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.



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.


Other Projects


Pharo 12 Adds New Breakpoint System
09/05/2024

The latest version of Pharo, the open-source Smalltalk-inspired language and core library adds a new breakpoint model based on the debug point system.



Amazon Bedrock Adds Support For Anthropic's Claude3 Opus
14/05/2024

Bedrock, Amazon's fully managed service for building generative AI applications, has been enhanced with support for Anthropic's Claude 3 Opus Foundation Model.


More News

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

<ASIN:1584885491>

<ASIN:1871962765>

<ASIN:1871962749>

<ASIN:1871962757>



Last Updated ( Saturday, 14 October 2023 )