关于 mongoose 中更新数据的问题

[fsy0718]

现在需要做一个可以无限分层级的项目
现在有 A 、 B 、 C 、 D 、 E 四个层级，设置 A 的父层级为 B ， B 的父层级为 C ， D 的父层级为 A
A -> B -> C
D -> A
我现在更新 C 层级时，将 C 的父层级指向 D ，造成一个闭环，如图
D - A - B -> C -> D
请问我应该怎么检测到成闭环，当更新 C 的父层级时，提示闭环

[Magic347]

如果分类之间的父级关系形成闭环，那么从该闭环中的任意一个分类节点不断向上寻找父分类的过程中，一定是可以最终回到起始分类节点的，利用这一点可以得到简单的闭环检测方法：

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

[Magic347]

事实上如果考虑一个更一般化的问题，那么这个问题就演变成一个在有向图内检测闭环的问题了。
解法会复杂一些，具体办法也是仿照上面的办法，只是需要枚举图内的所有节点，依次判断以每个节点作为起始节点深度优先遍历该图时是否形成环路。一旦发现任意节点存在环路的话，就认为该有向图是存在闭环的。
例如类似这样的图关系： 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

[isayme]

搜索 [链表 闭环]

[fsy0718]

谢谢