Re: [请益] linked list里如何找cycle?

楼主: DJWS (...)   2013-10-08 23:54:01
※ 引述《nikeasyanzi (nikeasyanzi)》之铭言:
: 想请问版上先进
: 如果只是单纯singal linking list
^^^^^^
singly
http://tw.dictionary.search.yahoo.com/search?p=singly
: 那可以用floyd's algorithm 即可解
: 但万一是任意node 允许连到两个以上相异点 类似m-way tree
: parent 可能不只有一个child
: 用floyd's algorithm不就解不了?
: 只能用kruskal algorithm 一个个edge加入来检查cycle这样 是嬷?
我猜你正在试着用图论的观点来看singly linked list
是的,这是个好办法,但是前提是:这个图必须是无向图,不能是有向图。
(严谨来说是kruskal's algorithm里面所用到的union-find algorithm)
如果是有向图,就必须用你推文提到的DFS、BFS。
DFS、BFS可以处理有向图,也可以处理无向图,比起kruskal's algortihm方便多了。
: 还是有其他更好的算法??
: 恳请赐教!
:
:
作者: nikeasyanzi (nikeasyanzi)   0000-00-00 00:00:00
感谢DJWS 大大的解说XD 我说的正是turtle&hare algo.只打floyd 造成误会 先说声抱歉XD
作者: scwg ( )   0000-00-00 00:00:00
原来它有名字 XDD
作者: singlovesong (~"~)   0000-00-00 00:00:00
讲floyd大家都会觉得是3个 for啦 loooooooooooool

Links booklink

Contact Us: admin [ a t ] ucptt.com