資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用 BFS 列印所有不可達節點的程式
不可達節點是圖中無法從特定源節點到達的節點。它們是無法在給定圖中與源節點互動的節點。識別不可達節點有助於確定圖中的孤立或斷開的實體。廣度優先搜尋 (BFS) 或深度優先搜尋 (DFS) 等演算法可用於遍歷圖並有效地標記已訪問的節點，從而有助於識別不可達節點。分析和理解不可達節點對於評估組織網路、識別資料或網路中的差距以及為組織最佳化和改進做出明智的決策至關重要。
該程式使用廣度優先搜尋 (BFS) 演算法來識別和列印給定圖中的所有不可達節點。這有助於評估組織結構，識別資料差距並做出明智的決策。BFS 演算法有效地遍歷圖以查詢孤立或不可訪問的節點。
使用的方法
BFS
BFS
BFS 代表廣度優先搜尋。它是一種圖遍歷演算法，它以廣度優先的順序探索圖的所有頂點，即它在移動到下一層之前訪問同一層的所有頂點。BFS 演算法從給定的源頂點開始，並探索其相鄰頂點。然後，它移動到下一層頂點，訪問它們的相鄰頂點，依此類推。它使用佇列資料結構來跟蹤要訪問的頂點。
演算法
初始化一個佇列和一個已訪問陣列
佇列是一種遵循先進先出 (FIFO) 原則的資料結構。它將用於在 BFS 遍歷期間儲存頂點。
已訪問陣列用於跟蹤已訪問或已探索的頂點。
將源頂點入隊並將其標記為已訪問
源頂點是 BFS 遍歷的起點。
入隊意味著將源頂點新增到佇列中。
將源頂點標記為已訪問可確保不會再次處理它。
執行 BFS 遍歷
重複以下步驟，直到佇列為空
從佇列中出隊一個頂點
出隊意味著從佇列的前面移除一個頂點。
將對出隊的頂點進行處理，並將它的相鄰頂點入隊。
將所有未訪問的相鄰頂點入隊
對於出隊頂點的每個相鄰頂點，如果它尚未訪問，則將其入隊。
此步驟確保以廣度優先的方式探索所有可達頂點。
將每個入隊的頂點標記為已訪問
在將每個頂點入隊後，將其標記為已訪問以避免再次訪問它。
列印未訪問的頂點。
完成 BFS 遍歷後，已訪問陣列將標記所有可從源頂點到達的頂點。
未訪問的頂點表示無法從源頂點到達的節點。
列印這些未訪問的頂點以識別圖中的斷開連線或不可達節點。
程式執行完成，並且已生成輸出。平滑退出程式。
示例 1
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Function to add an edge to graph
void addEdge(vector<int> adj[], int v, int w)
{
// Add w to v's list.
adj[v].push_back(w);
// Add v to w's list.
adj[w].push_back(v);
}
// BFS traversal of the vertices
// reachable from starting node
void findNonReachableNodes(vector<int> adj[], int s, int v)
{
// Mark all the vertices
// as not visited
bool visited[v] = {false};
// Create a queue for BFS
queue<int> q;
// Mark the current node as
// visited and enqueue it
q.push(s);
visited[s] = true;
while (!q.empty())
{
// Dequeue a vertex from
// queue
int p = q.front();
q.pop();
// Get all adjacent vertices
// of the dequeued vertex p.
// If an adjacent has not been
// visited, then mark it
// visited and enqueue it
for (auto it = adj[p].begin(); it != adj[p].end(); it++)
{
if (!visited[*it])
{
visited[*it] = true;
q.push(*it);
}
}
}
for (int i = 0; i < v; i++)
{
if (!visited[i])
{
cout << i << " ";
}
}
cout << "\n";
}
// Driver code
int main()
{
// Create a graph given in
// the above diagram
const int numVertices = 8;
vector<int> adj[numVertices];
addEdge(adj, 7, 1);
addEdge(adj, 6, 2);
addEdge(adj, 5, 7);
addEdge(adj, 4, 3);
addEdge(adj, 3, 4);
addEdge(adj, 1, 6);
findNonReachableNodes(adj, 0, numVertices);
return 0;
}
輸出
1 2 3 4 5 6 7
示例 2
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void addEdge(vector<vector<int>>& adjList, int v, int w) {
adjList[v].push_back(w);
adjList[w].push_back(v);
}
void findNonReachableNodes(vector<vector<int>>& adjList, int source, int numVertices) {
vector<bool> visited(numVertices, false);
queue<int> q;
q.push(source);
visited[source] = true;
while (!q.empty()) {
int vertex = q.front();
q.pop();
for (auto neighbor : adjList[vertex]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
for (int i = 0; i < numVertices; i++) {
if (!visited[i]) {
cout << i << " ";
}
}
cout << endl;
}
int main() {
const int totalVertices = 8;
vector<vector<int>> adjList(totalVertices);
addEdge(adjList, 0, 1);
addEdge(adjList, 0, 2);
addEdge(adjList, 1, 2);
addEdge(adjList, 3, 4);
addEdge(adjList, 4, 5);
addEdge(adjList, 6, 7);
int sourceVertex = 0;
findNonReachableNodes(adjList, sourceVertex, totalVertices);
return 0;
}
輸出
3 4 5 6 7
結論
本文闡明瞭使用廣度優先搜尋 (BFS) 演算法在圖中查詢不可達節點的概念。它討論了在分析組織系統、識別資訊或系統中的差距以及為系統最佳化和改進做出明智決策時識別不可達節點的重要性。逐步描述了 BFS 演算法，重點介紹了不可達節點的初始化、遍歷處理和列印。給出了一個程式示例來說明在圖中查詢不可達節點的 BFS 執行。本文旨在清晰地理解 BFS 及其在識別不可達節點中的應用。
85 次檢視
