回 帖 发 新 帖 刷新版面

主题:图的遍历问题,以及相关问题,请大家不吝指教

我想写一个图的遍历算法。
刚才就深度优先和广度优先算法在网上搜了一下,发现它们不是我想要的。因为它们从当前结点寻找下一个未访问结点时,目标结点与当前结点之间并不一定是连通的。而这不是我想要的。我想写的是如下一个加强的遍历结果:1,所有结点都访问过;2,最后的结果出来,相邻结点之间是连通的。换句话说,假设按着最后的结果浏览图,应该1,不走回路,2,可以走通,3,走遍所有结点。
尽量把我的需求表述得清楚一些,只是希望大侠告诉我,有没有类似的算法,这个算法叫什么名字,然后我可以在网上搜搜,我现在自己写的的程序,感觉在结点与边的存储方式上不适合解决我的需求。
我离开学校半年了,没有数据结构的书。所以,大家就不要让我自己去翻书了吧。如果哪位有相关的电子书或者是网上资源,麻烦传给我一下,谢谢:huangyingw@gmail.com。
我在网上搜到的很多是万方或者是维普的,需要注册才能浏览。大家知道哪有免费的镜像入口吗?是不是还得从教育网里找入口?
呵,如果哪位大侠有空,麻烦把你要用到的数据类型的定义帖上来让小弟参考一下。

回复列表 (共7个回复)

沙发

不知道你说的具体意思。不知道C#中的冒泡算法行不行。

板凳

呵,我刚修改了一下。
冒泡应该不行

3 楼

你要实现遍历,而且每个相邻点是连通,实际上就是要找出一条遍历所有节点,且每个节点只访问一次的路径,这是汉密而顿(hamiltonian)问题,是NP完全的

4 楼

呵,谢谢了,顺便问一下,这个问题,有没有现在的代码?
快忘掉了,好像算法里面有一个分治算法可以用来处理这个问题。
不知道我说的对吗,望不吝指教

5 楼

Hamilton图成立的充要条件尚未得到解决,是图论求解的课题之一

6 楼

因为是NP完全的
所以现在还没有能在多项式时间里解决的算法
现成的代码吗,你可能要去网上搜搜

7 楼

O(n!) in NP

我来回复

您尚未登录,请登录后再回复。点此登录或注册