构建一个算法，将两个 DAG 作为输入，Returns 在两个 DAG 中找到的最长路径
Constructing an Algorithm which takes as Input Two DAG's and Returns the Longest Path found in Both
Construct and describe an efficient algorithm which takes as input two directed acyclic graphs (DAG's) and finds the longest path which occurs in both of them.
If there are several, the algorithm should return one of the longest paths (it doesn't matter which one). In summary, given the graphs G = (V,E) and G' =(V',E'), find the longest possible sequence <v1,...,vk> where (v_i,v_{i+1}) is in E and E' for i = 1...k-1.
有什么想法吗？我可以自己编写实际代码，我只需要帮助构建实际算法背后的想法并找到问题的解决方案。
我想我可以使用递归 DFS 和一些记忆：同时跟踪访问过的节点；对于每个起始节点和每个邻居，计算到邻居的距离+邻居到目标的距离。然后取这些最大值，将其作为该节点的最大值记忆，并返回。
对两个 DAG 使用这种方法，这里的问题是确定在这两个路径中哪条路径最长。
将不胜感激 ideas/help。
两种方法：
从每个顶点出发，找出最长的公共路径是什么。 DFS+记忆。 Return 最大长度。如果你也想要路径，请记住最长的路径。
找到DAG的交点和return最长的相交路径。您可以找到 here 图形交集的代码。同样，您也可以为 DAG 做。
方法一中，不需要存储DAG的相交部分，只需要最大长度即可。因此，与方法二相比，它的内存效率更高。
在第一种方法中，您找出最大匹配路径的长度（此处为 BCD）和 return 长度。
在第二种方法中，您将存储匹配部分（此处为 BCD）和 return 从中得出的最长路径长度。
方法三：
@"n.1.8e9-where's-my-share m."在评论中提到另一种方法，您可以从一个图中删除另一个图中不存在的边。
因此，如果您从图 1 中删除图 2 中不存在的边，您将得到以下结果：
在上图中，如果您执行 DFS，您将得到 3 作为答案，因为 BCD 是最长的路径。
Construct and describe an efficient algorithm which takes as input two directed acyclic graphs (DAG's) and finds the longest path which occurs in both of them.
If there are several, the algorithm should return one of the longest paths (it doesn't matter which one). In summary, given the graphs G = (V,E) and G' =(V',E'), find the longest possible sequence <v1,...,vk> where (v_i,v_{i+1}) is in E and E' for i = 1...k-1.
有什么想法吗？我可以自己编写实际代码，我只需要帮助构建实际算法背后的想法并找到问题的解决方案。
我想我可以使用递归 DFS 和一些记忆：同时跟踪访问过的节点；对于每个起始节点和每个邻居，计算到邻居的距离+邻居到目标的距离。然后取这些最大值，将其作为该节点的最大值记忆，并返回。
对两个 DAG 使用这种方法，这里的问题是确定在这两个路径中哪条路径最长。
将不胜感激 ideas/help。
两种方法：
从每个顶点出发，找出最长的公共路径是什么。 DFS+记忆。 Return 最大长度。如果你也想要路径，请记住最长的路径。
找到DAG的交点和return最长的相交路径。您可以找到 here 图形交集的代码。同样，您也可以为 DAG 做。
方法一中，不需要存储DAG的相交部分，只需要最大长度即可。因此，与方法二相比，它的内存效率更高。
在第一种方法中，您找出最大匹配路径的长度（此处为 BCD）和 return 长度。
在第二种方法中，您将存储匹配部分（此处为 BCD）和 return 从中得出的最长路径长度。
方法三：
@"n.1.8e9-where's-my-share m."在评论中提到另一种方法，您可以从一个图中删除另一个图中不存在的边。
因此，如果您从图 1 中删除图 2 中不存在的边，您将得到以下结果：
在上图中，如果您执行 DFS，您将得到 3 作为答案，因为 BCD 是最长的路径。