试题详情
简答题简述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是非连通图或非强连通图，在这种情况下不存在最小生成树。

  • 关注下方微信公众号，在线模考后查看

热门试题