破圈法？？

amyxia · 发表于 2003-8-23 20:15:12

那天看一个图论的题目也是寻找最小路径（加权无向连通图），书上说用破圈法？？
哪位高手可以解释一下这个方法呢？3Q先了[em05]

飞云0616 · 发表于 2003-8-23 20:22:19

破圈就是：
Step1：去掉最大的权的边
Step2：判断是否是连通的：yes——》Step1；
not——》Step33；
Step3：不去该边，在不含该边的里面去掉最大边——》Step2；
Step4：没有边可去，结束；

飞云0616 · 发表于 2003-8-23 20:27:50

我的看法不全面，高手加加啊

Newton1983 · 发表于 2003-8-23 20:32:54

关于破圈法可以参考清华大学出版的运筹学的第六章.
另外寻找最小路径还可以用避圈法.

golden · 发表于 2003-8-23 22:02:10

就是为了不转圈，而去掉部分边。前题是不改变结果

batjh349 · 发表于 2003-8-29 06:13:55

破圈法就是求最小生成树的一种算法，在数据结构书上有现成的／／

haolaoban · 发表于 2003-8-29 23:36:43

破圈法其实就是,按照点不重复,保证不能让三条边构成一个回路了,其实说百了就是把所有的点联系起来,但不能两两有回路,着就是说对每一个图形来说,破圈法有很多种了!

haolaoban · 发表于 2003-8-29 23:37:24

破圈法其实就是,按照点不重复,保证不能让三条边构成一个回路了,其实说百了就是把所有的点联系起来,但不能两两有回路,着就是说对每一个图形来说,破圈法有很多种了!

		自动登录	找回密码
密码			注-册-帐-号