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()