无极平台网站,深圳市前十的互联网推广公司,建立企业网站的形式,应用软件开发平台今天来介绍第二部分#xff0c;图论中非常重要的知识点——最小生成树。作为数据结构的理论知识#xff0c;Prim算法和克鲁斯卡尔算法的思想此处博主不详细介绍#xff0c;建议在阅读本帖前熟练掌握。 对于无向带权图#xff0c;在MATLAB中可以直接以邻接矩阵的方式创建出来…今天来介绍第二部分图论中非常重要的知识点——最小生成树。作为数据结构的理论知识Prim算法和克鲁斯卡尔算法的思想此处博主不详细介绍建议在阅读本帖前熟练掌握。 对于无向带权图在MATLAB中可以直接以邻接矩阵的方式创建出来如下
A[0 20 0 0 15 0;20 0 20 60 25 0;0 20 0 30 18 0;0 60 30 0 35 10;15 25 18 35 0 15;0 0 0 10 15 0];
Ggraph(A);
但是这种创建方式对于可视化并不是很友好——无法在图上显示每条边对应的权值因此采用下面的方式创建
s[1 1 2 2 2 3 3 4 4 5];
t[2 5 3 4 5 4 5 5 6 6];
weights[20 15 20 60 25 30 18 35 10 15];
Ggraph(s,t,weights);
plot(G,EdgeLabel,weights);
创建出的带全无向图如下 首先我们先用普利姆算法手写一遍得出的答案如下 然后用MATLAB计算并可视化用到内置函数minspantree
Tminspantree(G);
plot(T);
计算结果如下 如图和博主手算的略微有区别其实是因为1——2与2——3两条边的权值一致所以最后找到的结点2无论和结点1还是结点3连接都正确~
