# 断开图的BFS

## 算法

1. 考虑，有 V 给定图中的节点。
2. 从0到V遍历每个节点，并寻找第一个未访问的节点。
3. 从该节点开始进行BFS遍历，并将随后遍历的所有节点标记为已访问。
4. 一旦访问了图中的所有节点，就终止。

## 代码

### 用于断开连接图的BFS的C ++程序

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// Add Edge from node u to v
void addEdge(vector <int> graph[], int u, int v)
{
graph[u].push_back(v);
}

// BFS traversal function
void BFS(vector <int> graph[], int n)
{
// vector to mark nodes as visited
vector <bool> vis(n,false);

// Process each node from 0 to n-1
for(int i=0;i<n;i++)
{
// If not visited node is found
if(vis[i] == false)
{
// BFS queue
queue <int> q;
// add not visited node to queue
q.push(i);

// BFS traversal
while(!q.empty())
{
int front = q.front();
q.pop();

cout<<front<<" ";

vis[front] = true;

for(auto node : graph[front])
{
if(vis[node] == false)
q.push(node);
}
}
}
}

cout<<endl;
}

int main()
{
// Construct the graph
int n = 7;
vector <int> graph[n];
vector<pair<int,int>> edges = {{1,0},{1,2},{2,5},{3,4},{4,6}};

for(auto e : edges)

// Display the BFS traversal
cout<<"BFS traversal of the given graph : ";
BFS(graph,n);

return 0;
}```
`BFS traversal of the given graph : 0 1 2 5 3 4 6`

### 用于断开连接图的BFS的Java程序

```import java.util.*;
import java.io.*;

class TutorialCup
{
// Add Edge from node u to v
static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v)
{
}

// BFS traversal function
static void BFS(ArrayList<ArrayList<Integer>> graph, int n)
{
// array to mark nodes as visited
boolean [] vis = new boolean[n];

// Process each node from 0 to n-1
for(int i=0;i<n;i++)
{
// If not visited node is found
if(vis[i] == false)
{
// BFS queue
Queue <Integer> q = new LinkedList<>();
// add not visited node to queue

// BFS traversal
while(!q.isEmpty())
{
int front = q.poll();

System.out.print(front+" ");

vis[front] = true;

Iterator itr = graph.get(front).iterator();
while(itr.hasNext())
{
int node = (Integer)itr.next();
if(vis[node] == false)

}
}
}
}

System.out.println();
}

public static void main (String[] args)
{
// Construct the graph
int n = 7;
ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<n;i++)

int [][] edges = {{1,0},{1,2},{2,5},{3,4},{4,6}};
for(int i=0;i<edges.length;i++)

// Display the BFS traversal
System.out.print("BFS traversal of the given graph : ");
BFS(graph,n);
}
}```
`BFS traversal of the given graph : 0 1 2 5 3 4 6`

## 复杂度分析

1. 时间复杂度：T（n）= O（V + E）
2. 空间复杂度：A（n）= O（V）

V =节点数。

E =边数。