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

求一个算法思路

  •  
  •   sankooc · 2016-12-06 10:37:12 +08:00 · 3266 次点击
    这是一个创建于 2891 天前的主题,其中的信息可能已经有所发展或是发生改变。

    输入是一个数组 数组元素数据结构是 { name: string, parent: string } name 是元素名 parent 是父节点名(可以为空)

    输出是对输入排序后的数组 排序规则为先把 parent 为空的元素前置,后置元素 parent 值肯定在前置元素中可以找到

    算法结果不仅要排序而且要找到 parent 对应错误的元素 而且侦查的到输入是否产生循环依赖

    我大概的思路是先生成一个多叉树再用前序遍历出来,但是现在找不出有效的方法根据数组生成多叉树

    3 条回复    2016-12-06 11:49:25 +08:00
    Umix
        1
    Umix  
       2016-12-06 11:16:19 +08:00
    先把 parent 为空的都找出来,作为 root node ,然后挨个看。比如第一个 root node 的 name 是 a ,那么遍历找一下有没有 parent 为 a 的,先发现了一个 d 后来发现一个 e ,那么按顺序插到 a 的后面,然后挨个遍历 d 和 e 的子节点继续插在后面,这么看发现也就是一个多叉树了。。。做完之后剩下的就是产生循环依赖的元素。。所以如果没理解错的话,是算法实现上卡住了?
    GtDzx
        2
    GtDzx  
       2016-12-06 11:19:49 +08:00
    拓扑排序?
    ddhwen
        3
    ddhwen  
       2016-12-06 11:49:25 +08:00 via Android
    拓扑排序吧,遍历输入用邻接表存图,同时记录节点度。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3479 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 10:44 · PVG 18:44 · LAX 02:44 · JFK 05:44
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.