• 欢迎加“百元导航”为主页,windows8风格,0.3s极速加载
  • 王柏元的博客专用搜索引擎:极客人,就用“极客搜”!
  •    1年前 (2015-11-15)  算法语言 |   抢沙发  34 
    文章评分 0 次,平均分 0.0
    [收起] 文章目录

    问题

    设给定一个任意的无向图,将图划分若干的子集,子集集合中任意俩个节点不相连,使用贪心算法使子集个数最少。

    算法步骤或流程:

     

    • 构造一个向量A按结点度大小加入。
    • 构建向量B为空,B存储最后的结果,其元素为子集
    • 取向量A的第一个元素m(即度最大)加入向量B,遍历B中的元素,如果m与B中元素(子集)中的元素都不相连,则加入到当前子集,如果相连则创建新子集。
    • 将向量A中m除去,重新对向量A按度大小排序,重复3

    无向图个数最少且元素间不相连的子集

    C++代码

     

     

    除特别注明外,本站所有文章均为王柏元的博客原创,为了尊重作者的劳动成果,转载请注明出处http://wangbaiyuan.cn/number-at-least-undirected-graph-elements-not-connected-subset-of.html,如果你觉得这篇文章对你有用,可以点击文章下面的“赞助作者”打赏作者!

    关于
    记录生活,镌刻心路;泼洒文墨,分享技术!王柏元的博客致力于IT经验交流,并原创翻译引进外文文章,打开IT国际化视野

    发表评论

    格式

    暂无评论

    登录

    忘记密码 ?

    您也可以使用第三方帐号快捷登录

    切换登录

    注册