# BFS for Disconnected Graph

In previous [post](https://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/), BFS only with a particular vertex is performed i.e. it is assumed that all vertices are reachable from the starting vertex. But in the case of disconnected graph or any vertex that is unreachable from all vertex, the previous implementation will not give the desired output, so in this post, a modification is done in BFS.

![](/files/-LclT0GZHhuUf2O6NMtL)

\
All vertices are reachable. So, for above graph simple [BFS](https://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/) will work

![](/files/-LclSwj_0DXOoDILtWWk)

\
As in above graph a vertex 1 is unreachable from all vertex, so simple BFS wouldn’t work for it.

```python
# Python3 implementation of modified BFS 
import queue 

# A utility function to add an edge 
# in an undirected graph. 
def addEdge(adj, u, v): 
	adj[u].append(v) 

# A utility function to do BFS of 
# graph from a given vertex u. 
def BFSUtil(u, adj, visited): 

	# Create a queue for BFS 
	q = queue.Queue() 
	
	# Mark the current node as visited 
	# and enqueue it 
	visited[u] = True
	q.put(u) 
	
	# 'i' will be used to get all adjacent 
	# vertices 4 of a vertex list<int>::iterator i 
	
	while(not q.empty()): 
		
		# Dequeue a vertex from queue 
		# and print it 
		u = q.queue[0] 
		print(u, end = " ") 
		q.get() 
	
		# Get all adjacent vertices of the 
		# dequeued vertex s. If an adjacent 
		# has not been visited, then mark 
		# it visited and enqueue it 
		i = 0
		while i != len(adj[u]): 
			if (not visited[adj[u][i]]): 
					visited[adj[u][i]] = True
					q.put(adj[u][i]) 
			i += 1

# This function does BFSUtil() for all 
# unvisited vertices. 
def BFS(adj, V): 
	visited = [False] * V 
	for u in range(V): 
		if (visited[u] == False): 
			BFSUtil(u, adj, visited) 

# Driver code 
if __name__ == '__main__': 

	V = 5
	adj = [[] for i in range(V)] 

	addEdge(adj, 0, 4) 
	addEdge(adj, 1, 2) 
	addEdge(adj, 1, 3) 
	addEdge(adj, 1, 4) 
	addEdge(adj, 2, 3) 
	addEdge(adj, 3, 4) 
	BFS(adj, V) 

# This code is contributed by PranchalK 

```

![](/files/-LclSnVrztwHOtZqk4Lx)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://stephanosterburg.gitbook.io/scrapbook/coding/python/breadth-first-search/bfs-for-disconnected-graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.