数据结构
网络
关系数据库管理系统 (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 次查看
