ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

EH搜索     
EH云课堂-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 EH云课堂直播课程免费学 打造核心竞争力的职场宝典
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
查看: 3105|回复: 2

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

[复制链接]

TA的精华主题

TA的得分主题

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

111.JPG


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

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

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

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

TA的精华主题

TA的得分主题

 楼主| 发表于 2012-9-23 22:40 | 显示全部楼层
有兴趣的来练练
算法、技巧,还有类模块

TA的精华主题

TA的得分主题

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

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

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


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

本版积分规则

关闭

最新热点上一条 /1 下一条

关注官方微信,高效办公专列,每天发车

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

GMT+8, 2020-2-26 09:18 , Processed in 0.383017 second(s), 17 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

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

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

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