推 nikeasyanzi:感謝DJWS 大大的解說XD 我說的正是turtle&hare algo. 10/09 00:08
→ nikeasyanzi:只打floyd 造成誤會 先說聲抱歉XD 10/09 00:09
→ scwg:原來它有名字 XDD 10/09 01:55
推 singlovesong:講floyd大家都會覺得是3個 for啦 loooooooooooool 10/09 11:05
※ 引述《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方便多了。
: 還是有其他更好的演算法??
: 懇請賜教!
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 111.251.199.98
: → scwg:這邊討論的 singly linked list 是用走一步走兩步線性解的吧 10/08 00:06
: → scwg:對任意 non-weighted graph 用 bfs 或 dfs 都可以只是要額外 10/08 00:09
: → scwg:空間 (或時間), 用不到 Floyd-Warshall 啊.. 10/08 00:09
你說的走一步走兩步應該是指原po所說的 floyd's algorithm 吧？
你可能把原po所說的 floyd's algortihm 誤會成別的東西了？
: 推 singlovesong:linked list 不准有兩個next吧? 10/08 08:57
yes... 既然現在是在討論 singly linked list 的話
: → nikeasyanzi:回scwg大:沒錯 若任意的graph 用DFS BFS 是可以的 10/08 14:34
: → nikeasyanzi:回singal link list是有定義只有一個node沒錯 10/08 14:36
: → nikeasyanzi:只是小弟想詢問 萬一不是link list 怎麼辦 10/08 14:37
: → nikeasyanzi:因為floyd 似乎只適用在只有一個child 的graph上!!?? 10/08 14:39
我猜你正在試著用圖論的觀點來看singly linked list
從圖論的觀點來看，你說的都十分正確～
更仔細一點來說，floyd只能用在有向圖，不能用在無向圖
: → scwg:你看的是哪裡的 floyd o_O 10/08 20:35
應該是這位吧 http://en.wikipedia.org/wiki/Robert_W._Floyd
至於原po所說的演算法，應該是文中提到的 floyd's cycle detection algorithm
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.130.84
※ 編輯: DJWS 來自: 36.225.130.84 (10/09 00:08)