最小生成树

一、【实验名称】

最小生成树(可视化实现)

二、【实验原理】

程序基于 Python 实现其中利用了 Tkinter 库作为可视化界面的制作，这是一款 Tkinter 是 Python 的标准 GUI 库。Python 使用 Tkinter 可以快速的创建 GUI 应用程序。

利用 Networkx 库，它内置了常用的图与复杂网络分析算法，可以方便的进行复杂网络数据分析、仿真建模等工作。对于本次实验图的可视化这部分，Networkx+Matplotlib 是一个很好的选择，操作方便而且功能多样。因此我选用了 Networkx+Matplotlib 作为图的可视化呈现。

python 程序生成应用程序选择了 Pyinstaller , 它的好处是可以把 python 环境和库放进去一起打包，因此不会受电脑环境的问题而无法执行，缺点就是存储占用有些大。

三、【实验内容】

3.1 代码解析：

``` importnetworkxasnx

importmatplotlib.pyplotasplt

importtkinterastk ```

调用三个库：Networkx 用于连接顶点形成图，matplotlib 用于配合 Networkx 显示图象，Tkinter 用于制作可视化输入台/控制台。

``` N=10005

Father=[0]+[n+1forninrange(N)]

R=[0]*(N+1)

_=1<<10

graph=[]

n=0 ```

定义图的相关定义。

python deffind(x):#并查集的find globalFather ifx==Father[x]: returnx Father[x]=find(Father[x]) returnFather[x]

定义并查集中的 find，用于 kruscal 算法中的搜索是否已加入最小生成树，防止成环。

python defunion(x,y):#并查集的union globalFather,R x=find(x) y=find(y) ifR[x]>R[y]: R[y],R[x]=R[x],R[y] Father[x]=y ifR[x]==R[y]: R[y]+=1

定义并查集中的合并，将顶点加入生成树，这里的 Union 还做了平衡处理，加快查找的速度。

defkruskal(G,num): E=[] foruinrange(num): forvinrange(num): ifu!=v: E.append((G[u][v],u+1,v+1)) T=set() for_,u,vinsorted(E): iflen(T)==num-1: break iffind(u)!=find(v): T.add((u,v)) union(u,v) returnT

kruscal 算法，用作寻找最小生成树，返回一个集合 Set，该集合即为最小生成树的边集。

c++ window=tk.Tk() window.title('MinimumSpanningTree(kruscal)') window.geometry('700x700')

创建一个窗口，窗口名为：MinimumSpanningTree(kruscal)，窗口大小为：700x700

I=tk.Label(window, text="pleaseinputthenumberofnodes:", font=('Arial',12), width=40,height=2) pack()

创建提示字模块，在窗口上显示：pleaseinputthenumberofnodes:

字体大小为 12，字体类型为 Arial，字模块宽 40，高 2

numofnodes=tk.Entry(window) numofnodes.pack()

创建一个文本输入框，放在提示字下方

=tk.Label(window, text="pleaseinputtheAdjacencyMatrix", font=('Arial',12), width=40,height=2) pack()

创建提示字模块，在窗口上显示：pleaseinputtheAdjacencyMatrix

字体大小为 12，字体类型为 Arial，字模块宽 40，高 2

data_mat=tk.Text(window,height=10) data_mat.pack()

创建一个文本输入框，放在提示字下方

``` definsert_data(): globaln n=int(numofnodes.get()) print(n) tep=data_mat.get("0.0","end").strip() graph=[[int(i)foriinrow.split('')]forrowintep.split('\n')]

graph.pop()#列表最后一个元素是空删除它

Gbefore=nx.Graph() print(graph[0][0]) foriinrange(n): forjinrange(n): if(graph[i][j]!=0): Gbefore.add_edges_from([(i+1,j+1)]) else: graph[i][j]=_ plt.figure(figsize=(15,7)) plt.subplot(1,2,1) plt.title("Theinputgraph:") nx.draw(Gbefore,with_labels=True,edge_color='black',node_color='orange',node_size=1000) G=nx.Graph() G.clear()

导入所有边，每条边分别用 tuple 表示

a_list=[]

G.add_edges_from(list(kruskal(graph,len(graph)))) print(len(graph)) plt.subplot(1,2,2) plt.title("MinimumSpanningTree'spictureafterusingKruscal") nx.draw(G,with_labels=True,edge_color='black',node_color='orange',node_size=1000) plt.show() ```

用作 button 的 command 功能：

输入数据，对接收到的文本框字符进行切片，转换为二维列表，同时要注意忽略结尾的空格或者回车，利用 stricp()函数即可。

对原图进行绘制：利用 networkx 的 add_edges_from 功能，并用 Matplotlib 来进行图像的显示。

执行 kruscal 算法，计算最小生成树。

对最小生成树进行绘制：利用 networkx 的 add_edges_from 功能，并用 Matplotlib 来进行图像的显示。

c++ b=tk.Button(window,text='Run',width=15,height=4,command=insert_data) pack() window.mainloop()

创建一个按钮：

显示名字为 Run

按钮大小为：长 15，高 4。

点击后触发 Insert_data 函数的功能

Window.mainloop()是让窗口不关闭

四、【小结或讨论】

在我一选到这门课的时候，实验室的学长就和我说杜老师的课有大作业，当时感到很有意思。

到了实验题目出来时，我列出了两个个方向去实现可视化界面：c++QT 和 python+ 库。因为对 c++ 比较熟悉，初步选择的是 c++QT，但是被语法劝退了，先学 QT 的话最少得一个星期多才能入门，我就去选择了 python 的方案。

同样也是零基础，只好先利用的 python 写出了 kruscal 的算法。然后花了一天来学习 Tkinter 来实现可视化控制台，摸索着查阅官网的文档和一些教学视频，终于学会一部分我可以用到的界面实现方法。然后又用了半天的时间学习 Networkx 库，说起来也是很幸运，这个假期看一门深度学习科普视频时有看到这个库用来显示神经网络层，我抱着试试的心态查询了下这个库，果真也有绘图的功能，于是半天看了些官方的文档，学到了一些基本要用到的函数。最后花了半天来用所学到的知识来做可视化界面。

我一直想做一个可视化界面的小软件，一直没机会去实现，很荣幸在这节课上完成了愿望，两天的时间学习了很多的东西，受益匪浅，我相信这些知识会在我未来研究生期间非常有用，也感谢老师给我们一个学习新知识的机会。由于时间并不充裕，这学期由于疫情课程安排十分紧凑，这个小软件做的还有很多缺陷，如果暑假有时间，我会继续完善它的其他功能，比如显示其他数据结构的可视化，希望最后这个软件可以用作教学示范，到时候我会 repo 到 GitHub 的仓库，记录一下这一段自己的成长。

最后，再次感谢老师的让我们做小项目的用意以及用心的选题，以后有机会的话我会推荐给实验室学弟这门有趣的课。

五、【源代码】

```python importnetworkxasnx importmatplotlib.pyplotasplt importtkinterastk 调用三个库：Networkx用于连接顶点形成图 matplotlib用于配合Networkx显示图象 Tkinter用于制作可视化输入台/控制台。 N=10005 Father=[0]+[n+1forninrange(N)] R=[0]*(N+1) _=1<<10 graph=[] n=0

定义图的相关定义。

text_content=[]#用来储存每一行内容的列表

定义并查集中的find

用于kruscal算法中的搜索是否已加入最小生成树，防止成环。

deffind(x):#并查集的find globalFather ifx==Father[x]: returnx Father[x]=find(Father[x]) returnFather[x]

定义并查集中的合并，将顶点加入生成树

这里的Union还做了平衡处理，加快查找的速度。

defunion(x,y):#并查集的union globalFather,R x=find(x) y=find(y) ifR[x]>R[y]: R[y],R[x]=R[x],R[y] Father[x]=y ifR[x]==R[y]: R[y]+=1

kruscal算法，用作寻找最小生成树，返回一个集合Set，该集合即为最小生成树的边集。

defkruskal(G,num): E=[] foruinrange(num): forvinrange(num): ifu!=v: E.append((G[u][v],u+1,v+1)) T=set() T.clear() for_,u,vinsorted(E): iflen(T)==num-1: break iffind(u)!=find(v): T.add((u,v)) union(u,v) returnT

用作button的command功能：

1.输入数据，对接收到的文本框字符进行切片，转换为二维列表，同时要注意忽略结尾的空格或者回车，利用stricp()函数即可。

2.对原图进行绘制：利用networkx的add_edges_from功能，并用Matplotlib来进行图像的显示。

3.执行kruscal算法，计算最小生成树。

4.对最小生成树进行绘制：利用networkx的add_edges_from功能，并用Matplotlib来进行图像的显示。

definsert_data(): globaln n=int(numofnodes.get()) print(n) tep=data_mat.get("0.0","end").strip() graph=[[int(i)foriinrow.split('')]forrowintep.split('\n')]