数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学给定图中节点的最长递增子序列长度
介绍
在图论中，用户将学习如何在指定图中查找节点的最长递增序列的长度。这包括在图中找到最长路径，其中路径中的每个节点的值都严格大于其前一个节点。在本文中，我们将探讨使用 C++ 解决此问题的三种方法。每种方法都将详细解释，包括算法、步骤执行和输出。为确保一致性，我们将对所有三种方法使用相同的输入，并且它们将产生相同的输出。
方法一：深度优先搜索 (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
方法三：广度优先搜索
第三种方法涉及使用广度优先搜索 (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++ 实现每种方法，并确保它们在给定相同输入的情况下产生相同的输出。通过应用这些方法，您将能够成功地确定不同图场景中节点的最长递增序列的长度。每种方法都有其自身的优点，并且可以根据问题的具体要求进行调整。
98 次查看
