有向图去环的解法

yiyiyicz · 发表于 2012-9-23 22:16

本帖最后由 yiyiyicz 于 2012-9-23 22:36 编辑

如上图所示：这是一幅有向图，而且是有向有环（有向边有两处断了，是粘贴出了点问题）
要求，有向图去环，变成有向无环图
去环后，结点不能少；有向边去掉的要少

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

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

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

yiyiyicz · 发表于 2012-9-23 22:40

有兴趣的来练练
算法、技巧，还有类模块

yiyiyicz · 发表于 2012-9-24 09:41

本帖最后由 yiyiyicz 于 2012-9-25 07:38 编辑

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

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

教材！有向无环图.rar (91.75 KB, 下载次数: 67)

		自动登录	找回密码
密码			免费注册

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