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