分支限界法 最小权顶点覆盖问题
★问题描述：给定一个赋权无向图G=(V,E),每个顶点v∈V都有一个权值w(v)。如果U∈V,且对任意(u,v)∈E有u∈U或v∈U,就称U为图G的一个顶点条覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖。
★算法设计：对于结定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖。
★数据输入：由文件input.txt给出输入数据。第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,.....,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2 个正整数u,v,表示图G的一条边(u,v)。
★结果输出：将计算出的最小权顶点覆盖的顶点权之和以及最优输出到文件output.txt.文件第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi,1≤i≤n,xi=0表示顶点i不在最小权顶点覆盖中。
文件下载
资源详情
[{"title":"（ 11 个子文件 363KB ） 分支限界法 最小权顶点覆盖问题","children":[{"title":"五、分支限界法","children":[{"title":"6-2.opt <span style='color:#111;'> 47.50KB </span>","children":null,"spread":false},{"title":"6-2.ncb <span style='color:#111;'> 41.00KB </span>","children":null,"spread":false},{"title":"Debug","children":[{"title":"vc60.pdb <span style='color:#111;'> 116.00KB </span>","children":null,"spread":false},{"title":"6-2.exe <span style='color:#111;'> 536.06KB </span>","children":null,"spread":false},{"title":"6-2.obj <span style='color:#111;'> 251.27KB </span>","children":null,"spread":false},{"title":"6-2.pdb <span style='color:#111;'> 1.05MB </span>","children":null,"spread":false}],"spread":true},{"title":"MinHeap.h <span style='color:#111;'> 1.58KB </span>","children":null,"spread":false},{"title":"6-2.dsp <span style='color:#111;'> 3.29KB </span>","children":null,"spread":false},{"title":"6-2.cpp <span style='color:#111;'> 3.63KB </span>","children":null,"spread":false},{"title":"6-2.dsw <span style='color:#111;'> 514B </span>","children":null,"spread":false},{"title":"6-2.plg <span style='color:#111;'> 733B </span>","children":null,"spread":false}],"spread":true}],"spread":true}]
评论信息
-
-
-
yehuiliusu :应付学校的昨夜完全够了 不过程序还有点小问题 运行出来的结果不是最优的2015-09-09 -
-
leedehua_ :同可用，不过和其他人的差不多2015-08-21
-
-
macchiatoo :还可以,但是结果跟书上的答案有出入啊2014-06-04
-
-
linyangfan94 :很好，好好研究研究2014-05-30
-
-
soareyou :还不错，及时的资料2013-10-23
-
其他资源
- 计算机原理硬件实验三（使用8251A的串行接口应用实验）（北理工）
- 计算机主板维修不是事儿.pdf
- 光纤光栅仿真代码
- C++实现IP数据包解析程序
- js完美实现同时拖拽、旋转、放大缩小图片的手势操作
- 机械设计二级减速器设计-CAD图纸全套
- 手机app蓝牙测试源码（hc-05蓝牙模块，适合初学者）
- C#3层架构+Winform操作XML文件(增删改查)
- Python代码 - 生成拉格朗日插值函数随插值点数量变化的gif动图
- 计算机网络技术FLASH课件(50个FLASH)
- linuxRTP打包发送
- iRead （免安装）
- stm32f103的stop模式测试例程
- MSP430F149最小系统板
- 电子信息专业 - 考研复试笔记分享（软件工程导论-第六版 + 管理信息系统-马慧）.rar
- S7-200与智能表485通讯程序
- 数值分析期末复习资料-福大研究生版.pdf
- koenker分位数回归
- 控件TChart（delphi经典例子）
- 戴尔R720 服务器2008 R2阵列卡驱动
- Arduino红外传感器库文件
- php简单某排班源码
- 操作系统实验 循环首次适应算法（C）
- 安卓即时通讯基于xmpp
- 西门子S7-200 PLC从入门到实践【程序源代码】
免责申明
【只为小站】的资源来自网友分享，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论 【只为小站】 经营者是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明
本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二条之规定，若资源存在侵权或相关问题请联系本站客服人员，zhiweidada#qq.com，请把#换成@，本站将给予最大的支持与配合，做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明