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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2264 天前的主题，其中的信息可能已经有所发展或是发生改变。

题目大概是这样的：
给定一张图，在图中增加若干个点和边，使得起点到到终点每条路径长度相同。示意图如下：

如图，左边路径到终点的距离为 3，右边路径距离为 2，因此应该在右边加一个节点，使得两边长度都为 3.

路径

到到

求思路

终点

15 条回复 • 2018-09-04 12:57:58 +08:00

twistoy

2018-09-04 10:03:06 +08:00 via Android

没要求加的点和边数量最小的话就很简单啊，dfs 或者 bfs 找到所有起点到终点的路径。然后都照着最长的加就可以了

PureWhiteWu

2018-09-04 10:05:12 +08:00

两次 DFS：第一次求出最长路径，第二次加电和边。

Bryan0Z

2018-09-04 10:23:18 +08:00

@twistoy
@PureWhiteWu
我画的图例子比较简单，要是负责了，点和边加在哪里，怎么加都是问题

takato

2018-09-04 10:34:38 +08:00

可以删除边吗？不然这题没有意义啊。。。

Bryan0Z

2018-09-04 10:39:32 +08:00 via Android

@takato 为啥没意义呀

pipapa

2018-09-04 10:53:56 +08:00 via Android

bfs 若没有到达终点就一直加点和边，保证同时到达。是否可行？

takato

2018-09-04 10:54:31 +08:00

@Bryan0Z 如果不能删除，你的例子中，右路的最短路径永远是 2 或 2 以下。

ihainan

2018-09-04 11:24:34 +08:00

这种情况，如果出现环，路劲这一概念是怎么定义的…如果是按 1 - 2 - 4 和 1 - 2 - 3 - 4，那无论怎么添加都是无解呀……

yemenchun1

2018-09-04 11:26:43 +08:00

虽然不是最优解, 但是考虑下带深度限制的 dfs?

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

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

2018-09-04 11:58:02 +08:00 via Android

@vegito2002 因为默认是 markdown 格式

Bryan0Z

2018-09-04 12:00:56 +08:00 via Android

@ihainan 我也想到了，我觉得他的意思是同一个节点不能重复走，或者这是个有向图

Bryan0Z

2018-09-04 12:01:56 +08:00 via Android

@takato 我没表述清楚哈，可以在边的中间加一个点，改变路径长度

twistoy

2018-09-04 12:57:58 +08:00 via Android

@Bryan0Z 首先，通过一次 dfs 求出来最大深度，也就是添加完边之后的期望深度。
这个问题就变成了给一个指定点，希望起点到这个点的所有路径的长度都是 N。
然后每个指定点的每个前驱，我们都会有一个深度的期望，这个问题就和原问题一样了，可以递归完成。
那对于每个点，它的不同后继会给它一个不同的深度期望，这个时候应该取最小的那个期望，作为它真正的深度期望，因为更深的期望可以通过在这个点和后继之间加边来完成。
大概这样。。。