Python编写最短连线程序

Question

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）可自定义连线规则（如只能直线，或者可以斜线）
现在前3个功能已经能实现，需要在次基础上加上第四个功能，给出完善后能够正确运行的代码，以及正确的运行结果界面截图

Answer 1

代码如下：（完整代码包含了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()

运行结果界面截图如下：