如何在无权一般图的所有简单路径中找到最长的递增子序列?

这里有一个非常快速的算法来解决这个问题。图中最长的递增子序列是图中路径的子序列,每条路径必须纯粹属于单个连接组件。因此,如果我们可以在连接组件上解决这个问题,我们可以通过在所有连接组件上找到最佳解决方案来解决整个图的问题。

1. 按权重排序所有节点,
2. 丢弃每个权重中除一个节点外的所有节点,以及
3. 通过依次访问每个节点来形成LIS。

总的来说,运行时是O(m+n+&Sort(n)),这比我以前的方法要好,应该更容易编写代码。

假设从图G中选择一条简单的路径,并查看该路径的最长递增子序列。虽然路径遍历整个图,并且可能有许多中间节点,但该路径的最长递增子序列实际上只关心

• 路径上的第一个节点也是LIS的一部分,并且
• 从该点开始,路径中的下一个最大值。

我们可以将此过程建模为在DAG中查找最长路径。DAG中的每个节点表示原始图G中的一个节点,如果存在,则存在从节点u到节点v的边

• G中有一条从u到v的路径,并且

这是一个DAG,因为第二个条件,即使原始图形不是DAG。

所以我们可以用两个步骤来解决这个整体问题。首先,构建上述DAG。为此:

1. 找到原始图G的连接分量,并用其连接分量编号标记每个节点。时间:O(m+n)。

2. 对于G中的每个节点u,在新的DAG D中构造相应的节点u'。时间:O(n)。

3. 对于G中的每个节点u,以及与u处于同一SCC中的每个节点v,如果w(u)<w(v),添加一条从u'到v'的边。时间:Θ(n ^2. )在最坏的情况下,Θ(n)在最好的情况下。

总运行时间:Θ(n ^2.