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("" , 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）可自定义连线规则（如只能直线，或者可以斜线）
现在前3个功能已经能实现，需要在次基础上加上第四个功能，给出完善后能够正确运行的代码，以及正确的运行结果界面截图
代码如下：（完整代码包含了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"]
def add_point(self, point):
self.points.append(point)
def add_edge(self, p1, p2, weight):
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:
self.add_edge(p1, p2, self.get_distance(p1, p2))
elif rule == "diag":
self.add_edge(p1, p2, self.get_distance(p1, p2))
else:
if self.get_distance(p1, p2) <= 100:
self.add_edge(p1, p2, self.get_distance(p1, p2))
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="Straight", variable=self.rule_var, value="straight").grid(row=2, column=1)
tk.Radiobutton(master, text="Diagonal", variable=self.rule_var, value="diag").grid(row=2, column=2)
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()
运行结果界面截图如下：
https://blog.csdn.net/lnotime/article/details/82313355
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) + '+20+20')
if self.cv is not None:
self.cv.delete('all')
self.Point_Label.destroy()
self.Entry_Points.destroy()
self.Random_Button.destroy()
self.Work_Button.destroy()
self.Check_Button.destroy()
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)
self.Point_Label = Label(self, text='点数:')
self.Point_Label.place(x=0, y=(self.Height_Number + 2) * size+10, width=Entry_Width, height=Entry_Height)
self.Entry_Points = Entry(self)
self.Entry_Points.place(x=Entry_Width, y=(self.Height_Number + 2) * size+10, width=Entry_Width,
height=Entry_Height)
self.Random_Button = Button(self, text='随机', command=self.Random_Number)
self.Random_Button.place(x=Entry_Width * 2, y=(self.Height_Number + 2) * size+10, width=Entry_Width,
height=Entry_Height)
self.Work_Button = Button(self, text='计算', command=self.WorkOut)
self.Work_Button.place(x=Entry_Width * 3, y=(self.Height_Number + 2) * size+10, width=Entry_Width,
height=Entry_Height)
self.CheckVar = IntVar()
self.Check_Button = Checkbutton(self, text='不能走斜线',variable= self.CheckVar,onvalue=1)
self.Check_Button.place(x=Entry_Width*4+30, y=(self.Height_Number + 2) * size+10, width=Entry_Width*2,
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
if self.CheckVar.get() == 1:
self.cv.create_line(x1, y1, x2, y1, width=3, fill=colors[j % len(colors)], tags=("line", str(j)+str(1)),
dash=(j+1, j+1))
self.cv.create_line(x2, y1, x2, y2, width=3, fill=colors[j % len(colors)], tags=("line", str(j)+str(2)),
dash=(j+1, j+1))
else:
self.cv.create_line(x1, y1, x2, y2, width=3, fill=colors[j % len(colors)], tags=("line", str(j)),
dash=(j+1, j+1))
if __name__ == "__main__":
window = GUI()
window.mainloop()
自己改了一下
其实你只完成了前两个问题，因为你是dfs计算出最短路径连线，点数多了就会耗费大量的时间，你设定斜线且点数少（不超过15个点）的情况还好说，如果你设定了只能连直线，那么需要dfs的点将会是棋盘里面所有的点数，你程序可能需要跑一年。综上所述，你的第三个问题不算做出来了。如果想做出自定义连线规则来，必须要重新设计计算最短路算法
这个问题和这个csdn文章里面的类似，可以参考一下：
https://blog.csdn.net/qq_35515661/article/details/86499957
如果以上回答对您有所帮助，点击一下采纳该答案～谢谢
```python
import math
def prim(points):
# 初始化
n = len(points)
mst = [] # 最小生成树的边集合
visited = [False] * n # 标记点是否被访问过
distances = [float('inf')] * n # 记录每个点到生成树的距离
distances[0] = 0 # 从第一个点开始
# Prim算法
for _ in range(n):
u = None
# 找到距离生成树最近的点
for i in range(n):
if not visited[i] and (u is None or distances[i] < distances[u]):
u = i
visited[u] = True
if u is not None:
# 将点u加入生成树
if distances[u] != 0:
# 将(u, parent[u])加入最小生成树
mst.append((points[u], points[parent[u]]))
# 更新与u相邻的点的距离
for v in range(n):
if not visited[v]:
dist = math.sqrt((points[u][0] - points[v][0]) ** 2 +
(points[u][1] - points[v][1]) ** 2)
if dist < distances[v]:
distances[v] = dist
parent[v] = u
return mst
# 测试
points = [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)] # 五个点的坐标
mst = prim(points)
print("最小生成树边集合：", mst)
```
内容来源与ChatGpt4及newbing和百度：
这是一个经典的旅行商问题（TSP），可以使用贪心算法、动态规划或遗传算法等方法来解决。其中贪心算法是最简单的解法，但不一定能得到最优解。下面是基于贪心算法的例子，假设有n个点，算法复杂度为O(n^2)：
points = [(1,2), (3,4), (5,6), (7,8), (9,10)] # 假设有5个点
distances = [] # 存储点之间的距离
for i, p1 in enumerate(points):
row = []
for j, p2 in enumerate(points):
if i == j:
row.append(0)
else:
row.append(math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2))
distances.append(row)
# 贪心算法
start = random.randint(0, n-1) # 随机选择起点
visited = [start]
while len(visited) < n:
last = visited[-1]
next = min(range(n), key=lambda x: distances[last][x] if x not in visited else float('inf'))
visited.append(next)
# 输出结果
print("->".join(str(i) for i in visited))
上面的代码中，先计算每个点之间的距离，然后随机选择一个起点，按照距离最近的顺序依次访问每个点，直到访问完所有点。最后输出结果为访问顺序。