求救：一个图里的最短回路怎么求？？各位大虾请帮忙

hanyaodong · 发表于 2003-8-15 06:54:52

[move]各位大虾请帮忙求救：一个图里的最短回路怎么求？？各位大虾请帮忙[/move]

wolfgang · 发表于 2003-8-15 07:08:38

通过遍历可以求出它的所有环，那样最短回路就可以求出来了。

由于遍历是对每个已经访问结点打标记，那么采用深度优先遍历时当回溯时候碰到一个以标记的结点时就表明找到了一个环。当然如果简单的做会产生很多重复的环，但是不影响求解。

飞云0616 · 发表于 2003-8-15 16:30:29

哈哈后

飞云0616 · 发表于 2003-8-15 16:31:46

是个好方法啊

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