PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [請益] linked list裡如何找cycle?

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間11年前 (2013/10/08 23:54)推噓2(2推 0噓 2→)

留言4則, 3人參與討論串3/3 (看更多)

※ 引述《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)