简述Kruskal算法的作用和具体步骤。
正确答案:K.ruskal算法用于最小生成树问题求解。对于有n个顶点的图G=(V,E),Kruskal算法根据图G中所有n个顶点生成一个包括n棵只有根结点的树Ti(i=0,1,…,n-1)的森林F,并按照以下规则森林F中的树合并,形成最小生成树:
A.从边集合E中选取未被访问过且具有最小权的边,置该边状态为已访问。判断该边的两个顶点是否属于不同的树,若属于不同的树则使用该边将两棵树合并为一棵;若属于同一棵树则不做任何处理。
B.重复上一步骤直至森林F中只剩下一棵树,该树即是图G的最小生成树。若最后森林F中剩下不止一棵树,则说明图G是非连通图或非强连通图,在这种情况下不存在最小生成树。
A.从边集合E中选取未被访问过且具有最小权的边,置该边状态为已访问。判断该边的两个顶点是否属于不同的树,若属于不同的树则使用该边将两棵树合并为一棵;若属于同一棵树则不做任何处理。
B.重复上一步骤直至森林F中只剩下一棵树,该树即是图G的最小生成树。若最后森林F中剩下不止一棵树,则说明图G是非连通图或非强连通图,在这种情况下不存在最小生成树。
答案解析:有
![](/editor/images/201705/qrcode_for_gh_573e2a458573_258.jpg)
微信扫一扫手机做题