试题详情
简答题 对下图所示的连通网络G，用克鲁斯卡尔（Kruskal）算法求G的最小生成树T，请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。
  • TE={（3，4），（2，3），（1，5），（4，6）（4，5）}
    贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。
    基本思想：首先将图中所有顶点都放到生成树中，然后每次都在连接两个不同连通分量的边中选权值最小的边，将其放入生成树中，直到生成树中有n-1条边。
    时间复杂度为：O（eloge）

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

热门试题