ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 3929|回复: 2

[讨论] 有向图去环的解法

[复制链接]

TA的精华主题

TA的得分主题

发表于 2012-9-23 22:16 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:
本帖最后由 yiyiyicz 于 2012-9-23 22:36 编辑

111.JPG


如上图所示:这是一幅有向图,而且是有向有环(有向边有两处断了,是粘贴出了点问题)
要求,有向图去环,变成有向无环图
去环后,结点不能少;有向边去掉的要少

解法不是一种
一般,先要将有向图用数据表示出来。常用的方法是矩阵法和链表
之后就是图的解法,这里名堂大了。比如可以用深度优先遍历,等等
最后,根据计算结果,再画出有向无环图。只要画出图来,自己就知道是不是正确。除了无环,还要保证结点数不变和边去掉的少这两个条件
用VBA代码肯定可以把数据算出来,图手工画就行了

深度优先的算法也不是一种,如染色,如递归等
如果用链表,注意不一定非要用物理指针。有相对关系就行了。比如用类模块构造出堆栈或者队列。看怎么用

版主不要把它移走,这之前曾和坛友讨论过。
做出来没有奖励,不分高下,只是兴趣,

TA的精华主题

TA的得分主题

 楼主| 发表于 2012-9-23 22:40 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
有兴趣的来练练
算法、技巧,还有类模块

TA的精华主题

TA的得分主题

 楼主| 发表于 2012-9-24 09:41 | 显示全部楼层
本帖最后由 yiyiyicz 于 2012-9-25 07:38 编辑

解上面的问题,有这样的一个思路
针对去环,土话说法是“如果两点之间存在两条路径,则去掉其中一条”。专业的说法就是“去掉遍历森林中的所有回边”

附上简单的教材
详细还是上网找吧,资料很多。因为这东西有用,实际应用越来越大!
网上还有各式各样的解法,用VBA代码的方法也有,EH中也有,但不全都是对的


教材!有向无环图.rar (91.75 KB, 下载次数: 67)
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-3-29 04:00 , Processed in 0.040767 second(s), 9 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表