【图论】【Matlab】最小生成树之Kruskal算法【贪心思想超详细详解Kruskal算法并应用】
实际问题引入实这道题的答案，其实就是找到这个图的最小生成树。
Kruskal算法
此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优
将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
在matlab中，最小生成树的生成直接用minspantree()函数就行。s=;
t=;
w=;
names={'1','2','3','4','5','6','7'};
G=graph(s,t,w,names);
p=plot(G,"EdgeLabel",G.Edges.Weight);
% 求解最小生成树
T=minspantree(G,"Method","sparse");
% sparse代表的是Kruskal算法
% dense代表的是Prim算法
% sparse:Kruskal算法
% 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
p=plot(G,"EdgeLabel",G.Edges.Weight);
highlight(p,T,"NodeColor","red","EdgeColor","red");
% 将最小生成树的边设置为红色!
生成的最小生成树：
我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声看到这里，相信我们已经学会Kruskal算法寻找最小生成树的过程了，当然，这离数学建模的要求，离我们的目标还非常遥远，博主在不断学习的过程中，也希望可以通过分享学习日记的方式带动大家！
页:
[1]