最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 数据结构:图(3)||最小生成树

    Prim算法

    keyword:从一个顶点起,顺顶点寻找,完成最小生成树的构建

    算法描述:从一个顶点开始,寻找与该结点连接的且不是弦且未被选中过的最短路,然后进入下一个结点,直到所有结点都被加入到生成树中。

    顶点的随机可以随机,prim算法保证任意选择都会得到正确的最小生成树。

    在教材中,使用到了辅助数组,释义

    其实使用的是一个结构体一维数组,array[i]记录了i结点目前距离树最近距离及结点,后面需要回溯时使用表格为依据,可完成快速跳转,每一次选择lowcost最小的结点i放入U中。

    使用不断更新这个表格,按照prim算法就可以得到最小生成树。

    代码部分就是更新k,选择结点,应该根据具体问题书写。

    Kruskal算法

    算法描述:最小生成树中,长度较小的边一定存在,将所有边按照长度顺序排列,将满足条件的边及结点分别加入到树中,直到所有结点都被加入到树种,这样也能得到唯一正确的最小生成树。

    keyword:边优先的最小生成树算法

    满足条件:是至少存在一个不在树中结点的最短弦

     

    将边按长度进行排序(根据这一题的性质,可以选择堆排序),取出,检查合法性,合法则加入到图中,不合法再次取出,直到堆空。

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 数据结构:图(3)||最小生成树

    发表评论

    • 52会员总数(位)
    • 312资源总数(个)
    • 31本周发布(个)
    • 3 今日发布(个)
    • 331稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情