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

请教个有向图的算法题

  •  
  •   aguesuka · 2021-05-29 16:05:06 +08:00 · 1782 次点击
    这是一个创建于 1256 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有两种表达式

    • A > B 代表有向图中, 点A可以到达点B, 而且两者不能是同一个点.
    • A >= B 代表有向图中, 点A可以到达点B, 或者两者是同一个点.

    输入表达式的列表, 判断是否满足有向无环图的条件:

    如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图

    例如

    • [A > B, B > C] 是一个有向无环图
    • [A >= B, B >= A] 是一个有向无环图, 其中 AB 被视为同一个点
    • [A > B, B >= A] 不是一个有向无环图

    直觉上有 O(n) 的算法.
    推广: 假设列表的前 x 项可以构成有向无环图,那么 x 的最大值是多少?
    如果第一个问题有 O(n) 的算法, 那么第二个问题可以使用第一个算法做遍历,时间复杂度是 O(n * n),是否有更优的算法?

    8 条回复    2021-05-30 09:31:23 +08:00
    YetToCome
        1
    YetToCome  
       2021-05-29 17:17:20 +08:00 via Android
    双指针
    geelaw
        2
    geelaw  
       2021-05-29 17:43:42 +08:00 via iPhone   ❤️ 2
    Tarjan 算法正是你所需要的。

    第二个问题很容易解答,有一个明显的 nlogn 算法,但是否可以降低到 n 我就懒得想了,可以试着找找强连通分量的在线算法。
    lance6716
        3
    lance6716  
       2021-05-29 19:22:22 +08:00 via Android
    [A >= B, B >= A] 是一个有向无环图, 其中 A 和 B 被视为同一个点

    当即可以解释为是,又可以解释为不是,要以”是有向无环图“优先
    akira
        4
    akira  
       2021-05-29 19:54:15 +08:00
    [A > B, B >= A] 这个怎么理解,A B 是不是同一个点
    aguesuka
        5
    aguesuka  
    OP
       2021-05-29 23:52:21 +08:00
    @akira 这种情况 A 和 B 不是同一个点, 所以 A > B > A 构成一个环. 可以把 A 和 B 看作类型为自然数的变量, `>=` 是大与小于, `>`是大于, 判断是否存在整数, 带入情况, 满足条件.
    aguesuka
        6
    aguesuka  
    OP
       2021-05-29 23:57:18 +08:00
    @geelaw 就是这个算法. 第二个问题, 二分法可以做到 O(n log n) , 我想的是在对问题一做了算法的判定以后, 在数组后追加一个表达式, 有没有小于线性时间的算法. 不过 strongly connected components algorithm 这个关键字已经足够了.
    sillydaddy
        7
    sillydaddy  
       2021-05-30 08:47:14 +08:00   ❤️ 1
    楼主的这个>, >=的抽象好简洁。能问一下是从什么里面抽象出来的问题啊?

    开始我想的方法,就是逐渐添加表达式,然后判断每一次添加,是否会造成环(所以对楼主的第二个问题感到奇怪)。然后发现每次添加新表达式后,总是要做一个“判断某个点是不是另一个点的父点”的操作,涉及到了查表。而查表的复杂度是 O(m)(m 是点的个数),导致最后复杂度是 O(n*m)。看到 @geelaw 提到的 Tarjan 算法,发现它巧妙的用动态构建的栈将这个查表的复杂度降到了 O(1),然而动态构建栈的代价是,建栈必须考虑整个图的所有连接信息,而如果是依次添加列表项,连接信息不完整,栈的方法就无效了。Tarjan 方法似乎和逐次添加列表项的方法是矛盾的。

    不知道楼主第 2 个问题的复杂度是多少,感觉降到了 O((n+m)log(n))已经是挺神奇了。
    aguesuka
        8
    aguesuka  
    OP
       2021-05-30 09:31:23 +08:00
    @sillydaddy 类型论中的隐式 Universe level 推导, 第二个问题其实就是完成某个函数的推导以后, 另一个调用其的函数是否能利用推导的结果. 理想是线性的, 现在看来不大可能, 也许需要找下相关源码或者 paper 看它们是怎么实现的.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5651 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 100ms · UTC 03:24 · PVG 11:24 · LAX 19:24 · JFK 22:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.