New update is available. Click here to update.

Last Updated: 7 Dec, 2020

Difficulty: Easy

```
1. Here, you need to consider that you need to print the BFS path starting from vertex 0 only.
2. V is the number of vertices present in graph G, and all vertices are numbered from 0 to V-1.
3. E is the number of edges present in graph G.
4. Graph input is provided as the number of vertices and a list of edges.
5. Handle for Disconnected Graphs as well.
```

```
Here, starting from 0, it is connected to 1 and 2 so, BFS traversal from here will be [0, 1, 2 ]. Now, 3 is also connected to 2. So, BFS traversal becomes [0, 1, 2, 3].
```

```
For each node, the correct order of printing the connected nodes will be sorted order, i.e., if {3,6,9,4} are connected to 1, then the correct order of their printing is {1,3,4,6,9}.
```

```
The first line of input contains two integers that denote the value of V and E.
Each of the following E lines contains space-separated two integers that denote an edge between vertex A and B.
```

```
For each test case, print the BFS Traversal, as described in the task.
Output for each test case will be printed in a separate line.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

```
0 <= V <= 10^4
0 <= E <= (V * (V - 1)) / 2
0 <= A <= V - 1
0 <= B <= V - 1
Where 'V' is the number of vertices, 'E' is the number of edges, 'A' and 'B' are the vertex numbers.
Time Limit: 1 second
```

Let us consider a function BFS that accepts a list of edges, EDGES, and the number of vertices VERTEX as a parameter and do:

- Create ADJACENCYMATRIX from EDGES.
- Define a boolean array VISITED to store nodes that are already visited.
- Iterate over VISITED[i] for each 0<= i < VISITED.LENGTH, and check:
- If VISITED[i] is FALSE, call BFSHELPER function for ADJACENCYMATRIX, i and VISITED.

Now, the function BFSHELPER accepts as parameters, an adjacency matrix of edges ADJACENCYMATRIX, an integer SOURCE and boolean array VISITED and do:

- Define a queue, ADJNODE, to store nodes under consideration but not added to the result.
- Create an ArrayList RESULT.
- Mark VISITED[SOURCE] as TRUE.
- Add SOURCE to queue ADJNODE.
- Iterate over queue elements until queue ADJNODE is EMPTY:
- Remove front element from ADJNODE and store it to FRONT
- Append FRONT to RESULT.
- Iterate over ADJACENCYMATRIX[FRONT][i] for 0<= i < ADJACENCYMATRIX.LENGTH and check:
- If any edge exists between FRONT and i, and i is not VISITED, mark VISITED[i] as TRUE and add i to ADJNODE.

- Return RESULT.

SIMILAR PROBLEMS

Valid Arrangement of Pairs

Posted: 28 Jan, 2022

Difficulty: Hard

Valid Arrangement of Pairs

Posted: 28 Jan, 2022

Difficulty: Hard

Valid Arrangement of Pairs

Posted: 28 Jan, 2022

Difficulty: Hard

Left Right Print

Posted: 9 Jul, 2022

Difficulty: Moderate

COUNT ISLANDS

Posted: 14 Sep, 2022

Difficulty: Moderate

The Summit

Posted: 15 Sep, 2022

Difficulty: Easy

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Popular Interview Problems: