資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在給定的非連通圖中，執行 Q 次查詢後，找到從 K 到 N 的第一個未刪除整數
簡介
在執行多個查詢後，從給定範圍內找到分離圖中主要的未刪除整數，可能是圖論中的一個具有挑戰性的問題。在本文中，我們研究了識別主要未刪除整數的任務，並提供了兩種使用 C++ 解決它的方法。每種方法都提供了不同的視角，並使用不同的演算法和資料結構。問題包括構建一個圖，將某些節點標記為已刪除，然後確定指定範圍內主要未刪除的整數。該圖表示節點之間的連線，而已刪除的節點是已移除或標記為無效的節點。
方法 1：深度優先搜尋 (DFS)
在這種方法中，我們使用圖的深度優先搜尋遍歷。我們從給定節點開始，遞迴地探索其鄰居。我們檢查已刪除的節點，並繼續遍歷，直到我們在所需的範圍內找到主要未刪除的整數。
演算法
步驟 1 - 構建圖。
步驟 2 - 檢查已刪除的節點。
步驟 3 - 執行深度優先搜尋 (DFS) 演算法來遍歷圖。
步驟 4 - 在 DFS 遍歷期間，檢查每個節點是否已刪除。
步驟 5 - 返回遇到的主要未刪除整數。
示例
#include <iostream>
#include <vector>
using namespace std;
vector<bool> traverse;
vector<bool> deleted;
vector<vector<int> > tg;
void dfs(int node, int& result) {
traverse[node] = true;
if (!deleted[node]) {
result = node;
return;
}
for (int i = 0; i < tg[node].size(); i++) {
int neighbor = tg[node][i];
if (!traverse[neighbor]) {
dfs(neighbor, result);
if (result != -1)
return;
}
}
}
int findFirstUndeleted(int K, int N) {
traverse.assign(N + 1, false);
int result = -1;
for (int i = K; i <= N; i++) {
if (!traverse[i]) {
dfs(i, result);
if (result != -1)
return result;
}
}
return result;
}
int main() {
int K = 1;
int N = 10;
// Construct the graph
tg.resize(N + 1);
// Add edges to the graph
// ...
// insert data at the end of the graph
// ...
tg[1].push_back(2);
tg[1].push_back(1);
tg[1].push_back(3);
tg[1].push_back(2);
tg[1].push_back(4);
// Set deleted nodes
deleted.resize(N + 1, false);
deleted[1] = true;
deleted[1] = true;
deleted[1] = true;
int firstUndeleted = findFirstUndeleted(K, N);
cout << "First undeleted integer: " << firstUndeleted << endl;
return 0;
}
輸出
First undeleted integer: 2
方法 2：廣度優先搜尋 (BFS)
在這種方法中，我們使用圖的廣度優先搜尋遍歷。我們從給定節點開始，使用佇列迭代地探索其鄰居。我們標記已刪除的節點，並繼續遍歷，直到我們在所需的範圍內找到主要未刪除的整數。
演算法
步驟 1 - 構建圖表。
步驟 2 - 檢查已刪除的節點。
步驟 3 - 實現廣度優先搜尋 (BFS) 演算法來遍歷圖表。
步驟 4 - 在 BFS 遍歷期間，檢查每個節點是否已刪除。
步驟 5 - 返回遇到的主要未刪除整數。
示例
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<bool> visited;
vector<bool> deleted;
vector<vector<int> > graph;
int findFirstUndeleted(int K, int N) {
visited.assign(N + 1, false);
queue<int> q;
int result = -1;
for (int i = K; i <= N; i++) {
if (!visited[i]) {
q.push(i);
visited[i] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
if (!deleted[node]) {
result = node;
break;
}
for (int j = 0; j < graph[node].size(); j++) {
int neighbor = graph[node][j];
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
if (result != -1)
break;
}
}
return result;
}
int main() {
int K = 1;
int N = 10;
// Construct the graph
graph.resize(N + 1);
// Add edges to the graph
// ...
// insert nodes
// ...
graph[1].push_back(2);
graph[2].push_back(1);
graph[2].push_back(3);
graph[3].push_back(2);
graph[3].push_back(4);
graph[4].push_back(3);
graph[4].push_back(5);
graph[5].push_back(4);
graph[6].push_back(7);
graph[7].push_back(6);
graph[8].push_back(9);
graph[9].push_back(8);
graph[10].push_back(5);
// Set deleted nodes
deleted.resize(N + 1, false);
deleted[2] = true;
deleted[5] = true;
deleted[7] = true;
int firstUndeleted = findFirstUndeleted(K, N);
cout << "First undeleted integer: " << firstUndeleted << endl;
return 0;
}
輸出
First undeleted integer: 1
結論
在本文中，我們研究了兩種在分離圖的給定範圍內查詢主要未刪除整數的方法。每種方法都提供了獨特的視角，並使用了不同的演算法和資料結構。方法 1 使用了深度優先搜尋 (DFS) 遍歷，方法 2 使用了廣度優先搜尋 (BFS) 遍歷。這些方法展示了處理該問題的不同策略，並且根據圖的特性和任務的要求，一種方法可能比另一種方法更適用。透過理解這些方法及其在 C++ 中的相應實現，使用者可以獲得關於有效解決類似基於圖的問題的見解。
50 次檢視
