資料結構
網路
關係資料庫管理系統 (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 次檢視
