Last Updated: 7 Dec, 2020

# BFS in Graph

Easy

## Problem statement

#### In this traversal, one can move from vertex 'u' to vertex 'v' only if there is an edge from 'u' to 'v'. The BFS traversal should include all nodes directly or indirectly connected to vertex 0.

##### Note:
``````The traversal should proceed from left to right according to the input adjacency list.
``````

##### Example:
``````Adjacency list: { {1,2,3},{4}, {5}, {},{},{}}

The interpretation of this adjacency list is as follows:
Vertex 0 has directed edges towards vertices 1, 2, and 3.
Vertex 1 has a directed edge towards vertex 4.
Vertex 2 has a directed edge towards vertex 5.
Vertices 3, 4, and 5 have no outgoing edges.

We can also see this in the diagram below.

BFS traversal: 0 1 2 3 4 5
``````

##### Input Format :
``````The first line contains two integers 'n' and 'm', where 'n' is the number of vertices in the directed graph, and 'm' is the number of directed edges in the graph.

The second line contains 'm' pairs of integers, representing the directed edges in the graph.
``````
##### Output Format :
``````The only line contains the BFS Traversal, as described in the task.
``````
##### Note:
``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````

## Approaches

### 01 Approach

#### Algorithm:

1. Create an empty array res to store the BFS traversal result.
2. Create an empty queue q for performing BFS.
3. Create an array vis of size n to mark visited vertices. Initialize all elements of vis to 0.
4. Start BFS from vertex 0 by enqueueing it in the queue q and marking it as visited in the vis array (vis[0] = 1).
5. While the queue q is not empty, perform the following steps: a. Dequeue the front vertex topVertex from the queue q. b. Add the topVertex to the result array res. c. Traverse all neighbors of topVertex (vertices reachable from topVertex through directed edges). d. For each neighbor neighbor:
• If neighbor is not visited (vis[neighbor] == 0), mark it as visited by setting vis[neighbor] = 1.
• Enqueue neighbor in the queue q for further traversal.
6. Return the BFS traversal result stored in the array res.