V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Bryan0Z
V2EX  ›  问与答

前几天被问了道算法题,求思路

  •  
  •   Bryan0Z · 2018-09-04 09:56:50 +08:00 · 2543 次点击
    这是一个创建于 2032 天前的主题,其中的信息可能已经有所发展或是发生改变。
    题目大概是这样的:
    给定一张图,在图中增加若干个点和边,使得起点到到终点每条路径长度相同。示意图如下:


    如图,左边路径到终点的距离为 3,右边路径距离为 2,因此应该在右边加一个节点,使得两边长度都为 3.
    15 条回复    2018-09-04 12:57:58 +08:00
    twistoy
        1
    twistoy  
       2018-09-04 10:03:06 +08:00 via Android
    没要求加的点和边数量最小的话就很简单啊,dfs 或者 bfs 找到所有起点到终点的路径。然后都照着最长的加就可以了
    PureWhiteWu
        2
    PureWhiteWu  
       2018-09-04 10:05:12 +08:00
    两次 DFS:第一次求出最长路径,第二次加电和边。
    Bryan0Z
        3
    Bryan0Z  
    OP
       2018-09-04 10:23:18 +08:00
    @twistoy
    @PureWhiteWu
    我画的图例子比较简单,要是负责了,点和边加在哪里,怎么加都是问题
    takato
        4
    takato  
       2018-09-04 10:34:38 +08:00
    可以删除边吗?不然这题没有意义啊。。。
    Bryan0Z
        5
    Bryan0Z  
    OP
       2018-09-04 10:39:32 +08:00 via Android
    @takato 为啥没意义呀
    pipapa
        6
    pipapa  
       2018-09-04 10:53:56 +08:00 via Android
    bfs 若没有到达终点就一直加点和边,保证同时到达。是否可行?
    takato
        7
    takato  
       2018-09-04 10:54:31 +08:00
    @Bryan0Z 如果不能删除,你的例子中,右路的最短路径永远是 2 或 2 以下。
    ihainan
        8
    ihainan  
       2018-09-04 11:24:34 +08:00


    这种情况,如果出现环,路劲这一概念是怎么定义的…如果是按 1 - 2 - 4 和 1 - 2 - 3 - 4,那无论怎么添加都是无解呀……
    yemenchun1
        9
    yemenchun1  
       2018-09-04 11:26:43 +08:00
    虽然不是最优解, 但是考虑下带深度限制的 dfs?
    vegito2002
        10
    vegito2002  
       2018-09-04 11:39:45 +08:00
    这题还是有点难的, 比如
    1---2---3
    | |
    4----5

    这种, 起点是 1, 终点是 3.
    为了补全 1-2-3 这条路径的长度, 点到底加在哪里还是有点讲究: 如果加在 1-2 之间肯定不行;

    更复杂一点都情况:
    1---2---3---4---5
    | / \ |
    ------6 8------

    起点是 1, 终点是 5 这种, 所有路线都没有公共前缀或者后缀, 暂时没想到一个很系统的思路.
    vegito2002
        11
    vegito2002  
       2018-09-04 11:43:08 +08:00
    第一张图是: [1=[2], 2=[1,3,4], 3=[2,5], 4=[2,5], 5=[3,4]]
    第二张图示: [1=[2,6], 2=[1,3], 3=[2,4,6,8], 4=[3,5], 5=[4,8], 6=[1,3], 8=[3,5]]
    V 站为什么要把所有的空格都删了...
    Bryan0Z
        12
    Bryan0Z  
    OP
       2018-09-04 11:58:02 +08:00 via Android
    @vegito2002 因为默认是 markdown 格式
    Bryan0Z
        13
    Bryan0Z  
    OP
       2018-09-04 12:00:56 +08:00 via Android
    @ihainan 我也想到了,我觉得他的意思是同一个节点不能重复走,或者这是个有向图
    Bryan0Z
        14
    Bryan0Z  
    OP
       2018-09-04 12:01:56 +08:00 via Android
    @takato 我没表述清楚哈,可以在边的中间加一个点,改变路径长度
    twistoy
        15
    twistoy  
       2018-09-04 12:57:58 +08:00 via Android
    @Bryan0Z 首先,通过一次 dfs 求出来最大深度,也就是添加完边之后的期望深度。
    这个问题就变成了给一个指定点,希望起点到这个点的所有路径的长度都是 N。
    然后每个指定点的每个前驱,我们都会有一个深度的期望,这个问题就和原问题一样了,可以递归完成。
    那对于每个点,它的不同后继会给它一个不同的深度期望,这个时候应该取最小的那个期望,作为它真正的深度期望,因为更深的期望可以通过在这个点和后继之间加边来完成。
    大概这样。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1531 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 48ms · UTC 17:06 · PVG 01:06 · LAX 10:06 · JFK 13:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.