如何在未加权一般图的所有简单路径中找到最长的递增子序列？
How to find longest increasing subsequence among all simple paths of an unweighted general graph?
设G = (V, E)是一个未加权的一般图，其中每个顶点v都有一个权重w(v).
G中简单路径p的递增子序列是p[=29的顶点序列=] 其中所有顶点的权重沿着这个序列增加。简单路径可以是闭合路径。
简单路径 p 的最长递增子序列 (LIS) 是 p 的递增子序列，其顶点数最大.
问题是，如何在G的所有简单路径中找到最长的递增子序列？
请注意，该图是无向的，因此它不是有向无环图 (DAG)。
这里有一个解决这个问题的非常快速的算法。图中最长的递增子序列是图中路径的子序列，并且每条路径必须纯属于单个连通分量。因此，如果我们可以在连接组件上解决这个问题，我们就可以通过在所有连接组件中找到最佳解决方案来解决整个图。
接下来，考虑一下您正在为连通图 G 解决此问题的情况。在这种情况下，您可以找到的最长递增子序列将通过按权重对节点进行排序，然后从最低权重节点到第二个，然后到第三个，然后到第四个，依此类推。如果有任何联系或重复，您可以跳过它们。也就是说，你可以通过
来解决这个问题
- 按权重对所有节点进行排序，
- 丢弃除每个权重的一个节点之外的所有节点，并且
- 依次访问每个节点形成一个LIS。
这导致对整个问题的算法非常快。在时间 O(m + n) 内，找到所有连接的组件。对于每个连通分量，在时间 O(Sort(n)) 中使用前面的算法，其中 Sort(n) 是对 n 个元素进行排序所需的时间（如果使用堆排序，则可能是 Θ(n log n)，Θ(n + U) 用于桶排序，Θ(n lg U) 用于基数排序，等等）。然后，return你找到的最长序列。
总体而言，运行时间为 O(m + n + &Sort(n))，这优于我之前的方法，并且应该更容易编写代码。
我最初发布了这个答案，我将保留它，因为我觉得它很有趣：
假设您从图 G 中选择了一条简单路径，并查看该路径的最长递增子序列。虽然路径遍历整个图并且可能有很多中间节点，但该路径的最长递增子序列实际上只关心
- 路径上的第一个节点也是 LIS 的一部分，并且
- 从那一点开始，路径中的下一个最大值。
因此，我们可以考虑像这样组建一个LIS。从图中的任何节点开始。现在，前往图中 (1) 的值高于当前节点且 (2) 可从当前节点到达的任何节点，然后根据需要重复此过程多次。目标是以给出最长可能的递增值序列的方式这样做。
我们可以将此过程建模为在 DAG 中寻找最长路径。 DAG中的每个节点代表原始图G中的一个节点，并且从节点u到节点v存在一条边if
- G中有一条从u到v的路径，并且
- w(u) < w(v).
由于第二个条件，这是一个 DAG，即使原始图不是 DAG。
所以我们可以分两步解决这个整体问题。首先，构建上述 DAG。为此：
找到原始图 G 的连通分量，并用连通分量编号标记每个节点。时间：O(m + n).
对G中的每个节点u，在新的DAG D中构造一个对应的节点u'。时间：O(n)。
对于 G 中的每个节点 u，以及 G 中与 u 位于同一 SCC 中的每个节点 v，如果 w(u) < w(v)，则添加一条从 u' 到v'。时间：最坏情况为Θ(n2)，最好情况为Θ(n).
求D中最长的路径。这条路径对应G中任意简单路径的最长递增子序列。时间：O(m + n).
总运行时间：最坏情况为 Θ(n2)，最佳情况为 Θ(m + n)。
设G = (V, E)是一个未加权的一般图，其中每个顶点v都有一个权重w(v).
G中简单路径p的递增子序列是p[=29的顶点序列=] 其中所有顶点的权重沿着这个序列增加。简单路径可以是闭合路径。
简单路径 p 的最长递增子序列 (LIS) 是 p 的递增子序列，其顶点数最大.
问题是，如何在G的所有简单路径中找到最长的递增子序列？
请注意，该图是无向的，因此它不是有向无环图 (DAG)。
这里有一个解决这个问题的非常快速的算法。图中最长的递增子序列是图中路径的子序列，并且每条路径必须纯属于单个连通分量。因此，如果我们可以在连接组件上解决这个问题，我们就可以通过在所有连接组件中找到最佳解决方案来解决整个图。
接下来，考虑一下您正在为连通图 G 解决此问题的情况。在这种情况下，您可以找到的最长递增子序列将通过按权重对节点进行排序，然后从最低权重节点到第二个，然后到第三个，然后到第四个，依此类推。如果有任何联系或重复，您可以跳过它们。也就是说，你可以通过
来解决这个问题- 按权重对所有节点进行排序，
- 丢弃除每个权重的一个节点之外的所有节点，并且
- 依次访问每个节点形成一个LIS。
这导致对整个问题的算法非常快。在时间 O(m + n) 内，找到所有连接的组件。对于每个连通分量，在时间 O(Sort(n)) 中使用前面的算法，其中 Sort(n) 是对 n 个元素进行排序所需的时间（如果使用堆排序，则可能是 Θ(n log n)，Θ(n + U) 用于桶排序，Θ(n lg U) 用于基数排序，等等）。然后，return你找到的最长序列。
总体而言，运行时间为 O(m + n + &Sort(n))，这优于我之前的方法，并且应该更容易编写代码。
我最初发布了这个答案，我将保留它，因为我觉得它很有趣：
假设您从图 G 中选择了一条简单路径，并查看该路径的最长递增子序列。虽然路径遍历整个图并且可能有很多中间节点，但该路径的最长递增子序列实际上只关心
- 路径上的第一个节点也是 LIS 的一部分，并且
- 从那一点开始，路径中的下一个最大值。
因此，我们可以考虑像这样组建一个LIS。从图中的任何节点开始。现在，前往图中 (1) 的值高于当前节点且 (2) 可从当前节点到达的任何节点，然后根据需要重复此过程多次。目标是以给出最长可能的递增值序列的方式这样做。
我们可以将此过程建模为在 DAG 中寻找最长路径。 DAG中的每个节点代表原始图G中的一个节点，并且从节点u到节点v存在一条边if
- G中有一条从u到v的路径，并且
- w(u) < w(v).
由于第二个条件，这是一个 DAG，即使原始图不是 DAG。
所以我们可以分两步解决这个整体问题。首先，构建上述 DAG。为此：
找到原始图 G 的连通分量，并用连通分量编号标记每个节点。时间：O(m + n).
对G中的每个节点u，在新的DAG D中构造一个对应的节点u'。时间：O(n)。
对于 G 中的每个节点 u，以及 G 中与 u 位于同一 SCC 中的每个节点 v，如果 w(u) < w(v)，则添加一条从 u' 到v'。时间：最坏情况为Θ(n2)，最好情况为Θ(n).
求D中最长的路径。这条路径对应G中任意简单路径的最长递增子序列。时间：O(m + n).
总运行时间：最坏情况为 Θ(n2)，最佳情况为 Θ(m + n)。