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