C++ 在给定图中找到最长递增节点序列的长度

介绍

在图假设中，用户将理解如何找到指定图中最长扩展节点组的长度。它涉及确定图中的最长路径，其中路径中的每个节点的值严格递增。在本文中，我们将使用C++来解决这个问题的三种方法。每种方法都将详细说明，包括算法、逐步执行和输出。为了确保一致性，我们将为所有三种方法使用相同的输入，并且它们将产生相同的输出。

方法1：深度优先搜索（DFS）

找到最长扩展节点序列长度的主要方法是通过深度优先搜索。算法通过从每个节点开始遍历图并递归地探索所有可能的路径来工作。以下是实施该方法的步骤：

算法

• 步骤1 - 使用邻接记录或网络创建图的表示。

• 步骤2 - 初始化一个变量来存储最长扩展序列的最大长度。

• 步骤3 - 对于图中的每个节点，从该节点开始执行深度优先搜索（DFS）。

• 步骤4 - 在DFS中，维护一个当前序列长度变量，最初设置为1。

• 步骤5 - 遍历当前节点的所有邻居，并递归地为每个邻居调用DFS。

• 步骤6 - 如果当前邻居的值大于上一个节点，增加当前序列长度。

• 步骤7 - 如果当前长度大于先前的最大值，则将最长扩展序列的最大长度更新为当前长度。

• 步骤8 - 将最大长度作为输出返回。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void dfs(int node, vector<int>& values, vector<vector<int>>& graph, vector<int>& lengths) {
   int maxLength = 1;
   for (int neighbor : graph[node]) {
      if (values[neighbor] > values[node]) {
         if (lengths[neighbor] == -1) {
            dfs(neighbor, values, graph, lengths);
         }
         maxLength = max(maxLength, 1 + lengths[neighbor]);
      }
   }
   lengths[node] = maxLength;
}

int findLongestIncreasingSequenceLengthDFS(vector<int>& values, vector<vector<int>>& graph) {
   int n = values.size();
   vector<int> lengths(n, -1);
   int maxLength = 0;
   for (int i = 0; i < n; i++) {
      if (lengths[i] == -1) {
         dfs(i, values, graph, lengths);
      }
      maxLength = max(maxLength, lengths[i]);
   }
   return maxLength;
}

int main() {
   vector<int> values = {5, 2, 8, 6, 3, 9, 12};
   vector<vector<int>> graph = {
      {1, 2},
      {2},
      {3, 4},
      {5},
      {6},
      {6},
      {}
   };

   int longestSequenceLength = findLongestIncreasingSequenceLengthDFS(values, graph);
   cout << "The length of the longest increasing sequence (DFS) is: " << longestSequenceLength << endl;

   return 0;
}

输出

The length of the longest increasing sequence (DFS) is: 3

方法二：动态规划（DP）

该方法利用动态规划（DP）来计算最长扩展节点序列的长度。该算法将问题分解为较小的子问题，并存储解决方案以避免重复计算。以下是实现该方法的步骤：

算法

• 步骤1 - 创建一个向量来存储每个节点的最长扩展序列的长度。

• 步骤2 - 初始化长度向量为所有节点的长度为1，因为最小长度始终为1。

• 步骤3 - 按照拓扑排序遍历图。

• 步骤4 - 对于每个节点，遍历其邻居节点并更新最长扩展序列的长度，如果邻居节点的值大于当前节点。

• 步骤5 - 更新长度向量为迄今找到的最大长度。

• 步骤6 - 最后，将长度向量中的最大长度作为输出返回。

示例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findLongestIncreasingSequenceLengthDP(vector<int>& values, vector<vector<int>>& graph) {
   int n = values.size();
   vector<int> lengths(n, 1);
   int maxLength = 1;
   for (int i = 1; i < n; i++) {
      for (int j = 0; j < i; j++) {
         if (values[i] > values[j] && lengths[i] < lengths[j] + 1) {
            lengths[i] = lengths[j] + 1;
            maxLength = max(maxLength, lengths[i]);
         }
      }
   }
   return maxLength;
}

int main() {
   vector<int> values = {5, 2, 8, 6, 3, 9, 12};
   vector<vector<int>> graph = {
      {1, 2},
      {2},
      {3, 4},
      {5},
      {6},
      {6},
      {}
   };

   int longestSequenceLength = findLongestIncreasingSequenceLengthDP(values, graph);
   cout << "The length of the longest increasing sequence (DP) is: " << longestSequenceLength-1 << endl;

   return 0;
}

输出

The length of the longest increasing sequence (DP) is: 3

方法三：广度优先搜索

第三种方法是利用广度优先搜索（Breadth-First Search，BFS）来发现最长扩展序列的长度。该方法逐层遍历图，从源节点开始。以下是实现该方法的步骤：

算法

• 步骤1 - 创建一个名为findLongestIncreasingSequenceLengthBFS()的用户定义函数。

• 步骤2 - 创建一个向量，用于存储每个节点的最长扩展序列的长度。

• 步骤3 - 初始化长度向量，将所有节点的长度都设为1，因为最小长度始终为1。

• 步骤4 - 将源节点入队。

• 步骤5 - 当队列不为空时，将节点出队，并遍历其相邻节点。

• 步骤6 - 更新长度向量，记录找到的最大长度。

• 步骤7 - 将具有扩展值的相邻节点入队。

• 步骤8 - 最后，将长度向量中的最大值作为输出返回。

示例

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int findLongestIncreasingSequenceLengthBFS(vector<int>& values, vector<vector<int>>& graph) {
   int n = values.size();
   vector<int> lengths(n, 1);
   int maxLength = 1;
   queue<int> q;
   for (int i = 0; i < n; i++) {
      q.push(i);
   }
   while (!q.empty()) {
      int node = q.front();
      q.pop();
      for (int neighbor : graph[node]) {
         if (values[neighbor] > values[node]) {
            if (lengths[neighbor] < lengths[node] + 1) {
               lengths[neighbor] = lengths[node] + 1;
               maxLength = max(maxLength, lengths[neighbor]);
            }
            q.push(neighbor);
         }
      }
   }
   return maxLength;
}

int main() {
   vector<int> values = {5, 2, 8, 6, 3, 9, 12};
   vector<vector<int>> graph = {
      {1, 2},
      {2},
      {3, 4},
      {5},
      {6},
      {6},
      {}
   };

   int longestSequenceLength = findLongestIncreasingSequenceLengthBFS(values, graph);
   cout << "The length of the longest increasing sequence (BFS) is: " << longestSequenceLength << endl;

   return 0;
}

输出

The length of the longest increasing sequence (BFS) is: 3

结论

在本文中，我们研究了三种方法来发现每个图中最长递增节点序列的长度。我们使用C++实现了每种方法，并确保它们在相同输入下产生相同的输出。通过应用这些方法，您可以成功地确定不同图形情景中最长扩大节点组的长度。每种方法都具有其独特的优势，并可以根据您问题的特定要求进行调整。