写一个可以和用户交互的python程序后续可打包为exe文件用户输入n个顶点和m条无向边使用prim返回最小生成图,权值已知
时间: 2024-02-23 17:57:22 浏览: 25
好的,以下是代码:
```python
import tkinter as tk
from tkinter import scrolledtext
import sys
import os
class Application(tk.Frame):
def __init__(self, master=None):
super().__init__(master)
self.master = master
self.pack()
self.create_widgets()
def create_widgets(self):
# 创建文本框和滚动条
self.textbox = scrolledtext.ScrolledText(self.master, width=80, height=20)
self.textbox.pack()
self.textbox.focus_set()
# 创建输入框和标签
self.prompt_label = tk.Label(self.master, text=">>>")
self.prompt_label.pack(side="left")
self.input_box = tk.Entry(self.master, width=60)
self.input_box.pack(side="left")
self.input_box.bind("<Return>", self.process_input)
def process_input(self, event):
# 处理用户输入
user_input = self.input_box.get()
self.input_box.delete(0, tk.END)
# 用户输入处理逻辑
response = self.process_user_input(user_input)
# 输出回复
self.textbox.configure(state='normal')
self.textbox.insert(tk.END, ">>> " + user_input + "\n")
self.textbox.insert(tk.END, response + "\n")
self.textbox.configure(state='disabled')
self.textbox.yview(tk.END)
def process_user_input(self, user_input):
# 在此处添加您的代码,根据用户输入返回回复
if not hasattr(self, 'graph'):
if ' ' in user_input:
n, m = map(int, user_input.split())
self.graph = [[] for _ in range(n)]
self.edges = []
self.visited = [False for _ in range(n)]
return "请输入每条边的起点、终点和权值,格式为:x y w"
else:
return "请输入顶点数n和边数m,用空格隔开"
else:
if ' ' in user_input:
x, y, w = map(int, user_input.split())
self.graph[x].append((y, w))
self.graph[y].append((x, w))
self.edges.append((x, y, w))
return "已添加边:%d-%d,权值为%d" % (x, y, w)
elif user_input == "show":
return self.show_graph()
elif user_input == "prim":
return self.prim()
else:
return "无效输入"
def show_graph(self):
# 输出图的邻接表
s = "图的邻接表:\n"
for i in range(len(self.graph)):
s += "%d: " % i
for j in range(len(self.graph[i])):
s += "(%d, %d) " % self.graph[i][j]
s += "\n"
s += "边列表:\n"
for edge in self.edges:
s += "%d-%d, 权值:%d\n" % edge
return s
def prim(self):
# prim算法求最小生成树
n = len(self.graph)
self.visited[0] = True
ans = 0
for _ in range(n - 1):
min_edge = None
for i in range(n):
if self.visited[i]:
for j, w in self.graph[i]:
if not self.visited[j] and (not min_edge or w < min_edge[2]):
min_edge = (i, j, w)
if not min_edge:
return "图不连通"
x, y, w = min_edge
self.visited[y] = True
ans += w
return "最小生成树权值:%d" % ans
def main():
root = tk.Tk()
root.title("Prim算法求最小生成树")
app = Application(master=root)
app.mainloop()
if __name__ == "__main__":
main()
```
这个程序使用Prim算法求最小生成树。首先,用户需要输入顶点数n和边数m,然后依次输入每条边的起点、终点和权值。用户可以使用 `show` 命令查看图的邻接表和边列表,使用 `prim` 命令求最小生成树的权值。如果用户输入不合法,程序会返回错误提示。程序会记录用户输入的所有边,最后输出最小生成树的权值。
如果您想将代码打包为exe文件,可以使用 `pyinstaller` 工具,具体操作方法可以参考这个链接:https://www.cnblogs.com/yoyoketang/p/11290551.html
希望能对您有所帮助!