artais 2023-04-13 15:46 采纳率: 63.2%

# Python编写最短连线程序

``````
from tkinter import *
import tkinter.messagebox
import itertools
import random
import math
import itertools

size = 50  # 定义方格的大小
r = 5  # 定义原点的半径
precision = 10  # 定义点击圆点精度范围
Entry_Width = 60
Entry_Height = 40

class GUI(Tk):
def __init__(self):
Tk.__init__(self)
self.Width_Number = 0
self.Height_Number = 0
self.Width = max((self.Width_Number + 2) * size, 400)
self.Height = (self.Height_Number + 3) * size
self.cv = None
self.Sign = [[0 for j in range(0, 101)] for i in range(0, 101)]
self.Entry_W = None
self.Entry_H = None
self.Entry_Points = None
self.title("最短连线程序")
self.geometry(str(self.Width) + 'x' + str(self.Height) + '+10+10')
self.init_input()
self.Min_Distance = 1e20
self.Line_Connect = None
self.distance = []

def Draw_Point(self, x_Num, y_Num):
x_Pos = x_Num * size
y_Pos = y_Num * size
if self.Sign[x_Num - 1][y_Num - 1]:
self.cv.delete(str(x_Pos) + '-' + str(y_Pos))
self.Sign[x_Num - 1][y_Num - 1] = 0
else:
self.cv.create_oval(x_Pos - r, y_Pos - r, x_Pos + r, y_Pos + r, fill="black",
tags=str(x_Pos) + '-' + str(y_Pos))
self.Sign[x_Num - 1][y_Num - 1] = 1

def Mouse_Button_Event(self, event):
# 获得点击位置最近的坐标
x_Num = round(event.x / size)
y_Num = round(event.y / size)
if x_Num > self.Width_Number + 1 or y_Num > self.Height_Number + 1 or x_Num == 0 or y_Num == 0:
return
x_Pos = x_Num * size
y_Pos = y_Num * size
if abs(event.x - x_Pos) < precision and abs(event.y - y_Pos) < precision:
self.Draw_Point(x_Num, y_Num)

def Generate(self):
try:
self.Width_Number = int(self.Entry_W.get())
self.Height_Number = int(self.Entry_H.get())
if self.Width_Number == 0 or self.Height_Number == 0 or self.Width_Number >= 100 or self.Height_Number >= 100:
tkinter.messagebox.showinfo('警告', '数字超出范围')
return
except ValueError:
tkinter.messagebox.showinfo('警告', '请输入数字')
return

self.Width = max((self.Width_Number + 2) * size, 400)
self.Height = (self.Height_Number + 3) * size
self.geometry(str(self.Width) + 'x' + str(self.Height) + '+10+10')
if self.cv is not None:
self.cv.delete('all')
self.cv.config(width=self.Width, height=self.Height)
else:
self.cv = Canvas(self, width=self.Width, height=self.Height, bg='white')
self.cv.pack()
for i in range(0, self.Width_Number):
for j in range(0, self.Height_Number):
self.cv.create_rectangle((i + 1) * size, (j + 1) * size, (i + 2) * size, (j + 2) * size)
self.cv.bind_all("<Button-1>", self.Mouse_Button_Event)
Label(self, text='点数:').place(x=0, y=(self.Height_Number + 2) * size, width=Entry_Width, height=Entry_Height)
self.Entry_Points = Entry(self.cv)
self.Entry_Points.place(x=Entry_Width, y=(self.Height_Number + 2) * size, width=Entry_Width,
height=Entry_Height)
Button(self.cv, text='随机', command=self.Random_Number).place(x=Entry_Width * 2,
y=(self.Height_Number + 2) * size,
width=Entry_Width, height=Entry_Height)
Button(self.cv, text='计算', command=self.WorkOut).place(x=Entry_Width * 3,
y=(self.Height_Number + 2) * size,
width=Entry_Width, height=Entry_Height)
self.init_input()

def init_input(self):
Label(self, text='列数:').place(x=0, y=0, width=Entry_Width, height=Entry_Height)
self.Entry_W = Entry(self)
self.Entry_W.place(x=Entry_Width, y=0, width=Entry_Width, height=Entry_Height)
Label(self, text='行数:').place(x=Entry_Width * 2, y=0, width=Entry_Width, height=Entry_Height)
self.Entry_H = Entry(self)
self.Entry_H.place(x=Entry_Width * 3, y=0, width=Entry_Width, height=Entry_Height)
self.Button_Generate = Button(self, text='生成', command=self.Generate)
self.Button_Generate.place(x=Entry_Width * 4, y=0, width=Entry_Width, height=Entry_Height)
self.Sign = [[0 for j in range(0, len(self.Sign[0]))] for i in range(0, len(self.Sign))]
self.Button_Clear = Button(self, text='清空', command=self.clear_Sign)
self.Button_Clear.place(x=Entry_Width * 5, y=0, width=Entry_Width, height=Entry_Height)

def clear_Sign(self):
self.clear_Line()
for i in range(0, self.Width_Number + 1):
for j in range(0, self.Height_Number + 1):
if self.Sign[i][j] == 1:
self.Draw_Point(i + 1, j + 1)

def clear_Line(self):
self.cv.delete("line")

def Random_Number(self):
try:
temp = int(self.Entry_Points.get())
except ValueError:
tkinter.messagebox.showinfo('警告', '请输入数字')
return
self.clear_Sign()
random_list = list(itertools.product(range(1, self.Width_Number + 2), range(1, self.Height_Number + 2)))
number = random.sample(random_list, temp)
for each in number:
x_Num = each[0]
y_Num = each[1]
self.Draw_Point(x_Num, y_Num)

def GetDistance(self, Point_List, i, j):
return math.sqrt(((Point_List[i][0] - Point_List[j][0]) ** 2) + ((Point_List[i][1] - Point_List[j][1]) ** 2))

# dfs计算出最短路径连线
def dfs(self,flag, index, sum, stack):
if sum > self.Min_Distance:
return
if len(stack) == len(flag):
if sum < self.Min_Distance:
self.Min_Distance = sum
self.Line_Connect = []
self.Line_Connect.append(list(stack))
return
elif sum == self.Min_Distance:
self.Line_Connect.append(list(stack))
return
else:
return
for j in range(0, len(flag)):
if flag[j] == 0:
flag[j] = 1
stack.append(j)
self.dfs(flag, j, sum+self.distance[index][j],stack)
flag[j] = 0
stack.pop()

def WorkOut(self):
Point_List = []
for i in range(0, self.Width_Number + 1):
for j in range(0, self.Height_Number + 1):
if self.Sign[i][j] == 1:
Point_List.append([i, j])
length = len(Point_List)
self.distance = [[self.GetDistance(Point_List, i, j) for j in range(0, length)] for i in range(0, length)]
self.Min_Distance = 10**10
self.Line_Connect = []
self.clear_Line()
stack = []
flag = [0 for i in range(0, length)]
for i in range(0, length):
flag[i] = 1
stack.append(i)
self.dfs(flag, i, 0, stack)
flag[i] = 0
stack.pop()

for each1 in self.Line_Connect:
for each2 in self.Line_Connect:
if each1[0] == each2[-1] and each1[-1] == each2[0]:
each2.reverse()
self.Line_Connect = list(set([tuple(t) for t in self.Line_Connect]))
colors = ["pink","red","blue","Violet","Purple","Navy","SkyBlue","Cyan","Green","Yellow","White"]
for j in range(0,len(self.Line_Connect)):
temp = random.randint(-5,5)
each = self.Line_Connect[j]
for i in range(0, len(each)-1):
x1 = (Point_List[each[i]][0]+1)*size+temp
y1 = (Point_List[each[i]][1]+1)*size+temp
x2 = (Point_List[each[i+1]][0]+1)*size+temp
y2 = (Point_List[each[i+1]][1]+1)*size+temp
self.cv.create_line(x1,y1,x2,y2,width=3,fill=colors[j%len(colors)],tags=("line",str(j)),dash=(4,4))

if __name__ == "__main__":
window = GUI()
window.mainloop()

``````

（1）可以自定义方格地图大小（aXb）
（2）可以设定点数，可以随机生成点，也可预置点的坐标
（3）生成最短连线，如不止一种结果，用多种颜色显示。
（4）可自定义连线规则（如只能直线，或者可以斜线）

• 写回答

#### 7条回答默认 最新

• 2301_77534089 2023-04-14 00:29
关注

代码如下：（完整代码包含了GUI界面的设计）

``````
import random
import math
import heapq
import tkinter as tk

class Point:
def __init__(self, x, y):
self.x = x
self.y = y

def __str__(self):
return f"{self.x},{self.y}"

class Edge:
def __init__(self, p1, p2, weight):
self.p1 = p1
self.p2 = p2
self.weight = weight

def __lt__(self, other):
return self.weight < other.weight

class Graph:
def __init__(self):
self.points = []
self.edges = []
self.colors = ["red", "blue", "green", "purple", "orange", "brown"]

self.points.append(point)

self.edges.append(Edge(p1, p2, weight))

def get_distance(self, p1, p2):
return math.sqrt((p1.x - p2.x)**2 + (p1.y - p2.y)**2)

def generate_points(self, n, width, height):
self.points = []
for i in range(n):
x = random.randint(0, width)
y = random.randint(0, height)
self.points.append(Point(x, y))

def draw_points(self, canvas):
for i, point in enumerate(self.points):
canvas.create_oval(point.x-2, point.y-2, point.x+2, point.y+2, fill=self.colors[i%len(self.colors)])

def draw_edge(self, canvas, p1, p2, color="black"):
canvas.create_line(p1.x, p1.y, p2.x, p2.y, fill=color)

def generate_edges(self, rule):
self.edges = []
for i in range(len(self.points)):
for j in range(i+1, len(self.points)):
p1 = self.points[i]
p2 = self.points[j]
if rule == "straight":
if p1.x == p2.x or p1.y == p2.y:
elif rule == "diag":
else:
if self.get_distance(p1, p2) <= 100:

def kruskal(self):
self.edges.sort()
parent = {}
for point in self.points:
parent[point] = point
mst = []
for edge in self.edges:
p1 = edge.p1
p2 = edge.p2
root1 = self.find(parent, p1)
root2 = self.find(parent, p2)
if root1 != root2:
mst.append(edge)
parent[root1] = root2
return mst

def find(self, parent, point):
if parent[point] == point:
return point
return self.find(parent, parent[point])

class App:
def __init__(self, master):
self.master = master
self.width = 800
self.height = 500
master.title("Shortest Path")

tk.Label(master, text="Number of Points:").grid(row=0, column=0)
self.num_points_entry = tk.Entry(master)
self.num_points_entry.grid(row=0, column=1)
self.num_points_entry.insert(0, "10")

tk.Label(master, text="Size of Grid:").grid(row=1, column=0)
self.grid_size_entry = tk.Entry(master)
self.grid_size_entry.grid(row=1, column=1)
self.grid_size_entry.insert(0, "800x500")

tk.Label(master, text="Connection Rule:").grid(row=2, column=0)
self.rule_var = tk.StringVar()
self.rule_var.set("straight")
tk.Radiobutton(master, text="Distance < 100", variable=self.rule_var, value="dist").grid(row=2, column=3)

self.generate_button = tk.Button(master, text="Generate", command=self.generate_points)
self.generate_button.grid(row=3, column=0)

self.canvas = tk.Canvas(master, width=self.width, height=self.height)
self.canvas.grid(row=4, column=0, columnspan=4)

self.solve_button = tk.Button(master, text="Solve", command=self.solve)
self.solve_button.grid(row=5, column=0)

self.show_all_button = tk.Button(master, text="Show All", command=self.show_all)
self.show_all_button.grid(row=5, column=1)

self.quit_button = tk.Button(master, text="Quit", command=master.quit)
self.quit_button.grid(row=5, column=3, sticky=tk.W)

self.rule_var.trace("w", lambda *_: self.generate_points())

self.graph = Graph()

def generate_points(self):
self.graph.generate_points(int(self.num_points_entry.get()), *map(int, self.grid_size_entry.get().split("x")))
self.graph.generate_edges(self.rule_var.get())
self.redraw()

def solve(self):
self.canvas.delete("all")
self.graph.generate_edges(self.rule_var.get())
mst = self.graph.kruskal()
for i, edge in enumerate(mst):
self.graph.draw_edge(self.canvas, edge.p1, edge.p2, color=self.graph.colors[i%len(self.graph.colors)])
self.graph.draw_points(self.canvas)
self.canvas.create_text(self.width//2, self.height-20, text=f"Minimum Total Weight: {min_total_weight:.2f}", font=("Arial", 16, "bold"))
self.canvas.update()

def redraw(self):
self.canvas.delete("all")
self.graph.draw_edges(self.canvas)
self.graph.draw_points(self.canvas)
self.canvas.update()

root = tk.Tk()
app = App(root)
root.mainloop()
``````

运行结果界面截图如下：

本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 问题事件

• 系统已结题 4月23日
• 已采纳回答 4月15日
• 赞助了问题酬金15元 4月13日
• 创建了问题 4月13日

#### 悬赏问题

• ¥15 为啥画版图在Run DRC会出现Connect Error？可我Calibre的hostname和计算机的hostname已经设置成一样的了。
• ¥20 网站后台使用极速模式非常的卡
• ¥20 Keil uVision5创建project没反应
• ¥15 mmseqs内存报错
• ¥15 vika文档如何与obsidian同步
• ¥15 华为手机相册里面的照片能够替换成自己想要的照片吗？
• ¥15 陆空双模式无人机飞控设置
• ¥15 sentaurus lithography
• ¥100 求抖音ck号 或者提ck教程
• ¥15 关于#linux#的问题：子进程1等待子进程A、B退出后退出(语言-c语言)