1
Magic347 2016-04-22 21:44:24 +08:00
如果分类之间的父级关系形成闭环,那么从该闭环中的任意一个分类节点不断向上寻找父分类的过程中,一定是可以最终回到起始分类节点的,利用这一点可以得到简单的闭环检测方法:
def check_loop(category): ____parent = category.get_parent() ____while parent is not None: ________if parent == category: ____________return True ________category = parent ________parent = category.get_parent() ____return False |
2
Magic347 2016-04-22 22:41:59 +08:00
事实上如果考虑一个更一般化的问题,那么这个问题就演变成一个在有向图内检测闭环的问题了。
解法会复杂一些,具体办法也是仿照上面的办法,只是需要枚举图内的所有节点,依次判断以每个节点作为起始节点深度优先遍历该图时是否形成环路。一旦发现任意节点存在环路的话,就认为该有向图是存在闭环的。 例如类似这样的图关系: A -> B <- C -> D -> E -> C def dfs_check_loop(node, has_loop, visited): ____for next_node in node.get_next_nodes(): ________if not visited[next_node]: ____________visited[node] = True ____________dfs_check_loop(next_node, has_loop, visited) ____________visited[node] = False ________else: has_loop = True def check_loop_graph(graph): ____for node in graph.get_all_nodes(): ________visited = {} ________visited[node] = True ________has_loop = False ________dfs_check_loop(node, has_loop, visited) ________if has_loop: ____________return True ____return False |
3
isayme 2016-04-23 05:38:02 +08:00 via iPhone
搜索 [链表 闭环]
|
4
fsy0718 OP 谢谢
|