資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在圖中找到 K 個與至少一個剩餘頂點相連的頂點
可以使用深度優先搜尋 (DFS) 來查詢網路中與至少一個剩餘頂點相連的 K 個頂點。您應該從剩餘頂點之一開始，然後對該頂點執行 DFS。在搜尋過程中遇到的每個頂點都將被記錄，並將其新增到類似頂點的集合中。找到 K 個頂點或搜尋完所有剩餘頂點後，重複此過程。DFS 透過仔細探索圖來找到仍然與至少一個剩餘頂點相連的 K 個頂點，從而幫助完成任務。
使用的方法
DFS
BFS
DFS
在查詢圖表中與至少一個剩餘頂點相連的 K 個頂點的情況下，可以使用深度優先搜尋 (DFS)。選擇剩餘頂點之一，然後從該頂點啟動 DFS。檢查在探索圖表時經過的每個頂點，並將其新增到連線頂點的集合中。繼續檢查圖表，直到構建了 K 個頂點，識別了標準或檢查了所有頂點。DFS 透過深度優先遍歷區分保持與至少一個剩餘頂點連線的 K 個頂點的證明，從而實現所需的目標。
演算法
初始化一個名為“connectedVertices”的集合，用於儲存 K 個頂點。
從剩餘頂點中選擇一個頂點“startVertex”。
為 DFS 遍歷建立一個名為“stack”的棧。
將“startVertex”壓入“stack”。
當“stack”不為空時，
從“stack”的頂部彈出一個頂點“currentVertex”。
將“current vertex”標記為已訪問。
將“currentVertex”新增到“connectedVertices”集合中。
遍歷“currentVertex”的相鄰頂點
如果相鄰頂點在剩餘頂點內且未訪問，
將相鄰頂點壓入“stack”。
重複步驟 2-5，直到所有 K 個頂點都被區分或所有剩餘頂點都被探索。
示例
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> findConnectedVertices(int startVertex, vector<vector<int>>& adjacencyList) {
int N = adjacencyList.size(); // Total number of vertices
vector<int> connectedVertices; // Set of connected vertices
vector<bool> visited(N, false); // Track visited vertices
stack<int> stack; // Stack for DFS traversal
stack.push(startVertex); // Push the startVertex onto the stack
while (!stack.empty()) {
int currentVertex = stack.top();
stack.pop();
if (!visited[currentVertex]) {
visited[currentVertex] = true;
connectedVertices.push_back(currentVertex);
for (int adjVertex : adjacencyList[currentVertex]) {
if (!visited[adjVertex]) {
stack.push(adjVertex);
}
}
}
}
return connectedVertices;
}
int main() {
int N = 7; // Total number of vertices
vector<vector<int>> adjacencyList(N);
// Add adjacency list for each vertex
adjacencyList[0] = {1, 2};
adjacencyList[1] = {0, 2};
adjacencyList[2] = {0, 1, 3};
adjacencyList[3] = {2, 4};
adjacencyList[4] = {3};
adjacencyList[5] = {6};
adjacencyList[6] = {5};
int startVertex = 0;
vector<int> connectedVertices = findConnectedVertices(startVertex, adjacencyList);
cout << "Connected Vertices: ";
for (int vertex : connectedVertices) {
cout << vertex << " ";
}
cout << endl;
return 0;
}
輸出
Connected Vertices: 0 2 3 4 1
BSF
在查詢圖表中與至少一個剩餘頂點相關的 K 個頂點的設定中，可以使用廣度優先搜尋 (BFS)。首先從剩餘頂點中選擇一個頂點，然後從該頂點執行 BFS。在查詢過程中，檢查每個經過的頂點並將其包含在關聯頂點的集合中。逐層檢查圖表，確保在移至另一層之前先經過更近距離的頂點。重複此準備工作，直到識別出 K 個頂點或檢查完所有剩餘頂點。透過以廣度優先的方式遍歷圖表，BFS 有助於識別保持與至少一個剩餘頂點關聯的 K 個頂點，從而完成手頭的任務。
演算法
建立一個名為 S 的集合來儲存關聯的頂點。
當 K > 且 R 不為空時，執行以下操作
a. 從 R 中選擇一個頂點 v。
b. 從 v 開始執行廣度優先搜尋 (BFS)。
c. 在 BFS 期間，標記每個經過的頂點並將其新增到 S 中。
d. 將 K 減 1。
e. 從 R 中移除 V。
返回包含 K 個關聯頂點的集合 S。
該演算法從剩餘頂點中選擇一個頂點，並對該頂點執行 BFS。它標記每個經過的頂點並將其包含在關聯頂點的集合中。該策略持續進行，直到識別出 K 個頂點或沒有剩餘頂點被清除。
示例
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
std::unordered_set<int> purgeVertices(int K, const std::vector<std::vector<int>>& graph) {
std::unordered_set<int> S;
std::vector<bool> visited(graph.size(), false);
auto bfs = [&](int start) {
std::queue<int> q;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
if (!visited[v]) {
visited[v] = true;
S.insert(v);
K--;
if (K == 0) {
return;
}
for (int neighbor : graph[v]) {
if (!visited[neighbor]) {
q.push(neighbor);
}
}
}
}
};
for (int i = 0; i < graph.size() && K > 0; i++) {
bfs(i);
}
return S;
}
int main() {
// Example usage
int K = 3;
std::vector<std::vector<int>> graph = {
{1, 2},
{0, 2, 3},
{0, 1, 3},
{1, 2}
};
std::unordered_set<int> result = purgeVertices(K, graph);
// Print the resulting set
std::cout << "Purged vertices: ";
for (int v : result) {
std::cout << v << " ";
}
std::cout << std::endl;
return 0;
}
輸出
Purged vertices: 2 1 0
結論
本文提供了一種演算法方法，用於查詢圖表中與至少一個剩餘頂點相關的 K 個頂點。該演算法利用深度優先搜尋 (DFS) 或廣度優先搜尋 (BFS) 來遍歷圖表並識別指定的頂點。它包含 C 中的程式碼片段，這些程式碼片段使用不同的函式來執行搜尋操作。本文旨在幫助軟體工程師理解和執行識別圖表中相關頂點的方法，從而促進依賴圖表網路的不同應用程式和檢查。
92 次檢視
