V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
fsy0718
V2EX  ›  Node.js

关于 mongoose 中更新数据的问题

  •  
  •   fsy0718 · 2016-04-22 16:38:33 +08:00 · 4835 次点击
    这是一个创建于 3119 天前的主题,其中的信息可能已经有所发展或是发生改变。
    现在需要做一个可以无限分层级的项目
    现在有 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 的父层级时,提示闭环
    4 条回复    2016-04-23 10:03:35 +08:00
    Magic347
        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
    Magic347
        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
    isayme
        3
    isayme  
       2016-04-23 05:38:02 +08:00 via iPhone
    搜索 [链表 闭环]
    fsy0718
        4
    fsy0718  
    OP
       2016-04-23 10:03:35 +08:00
    谢谢
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1686 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 16:44 · PVG 00:44 · LAX 08:44 · JFK 11:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.