Solution: Implement Breadth-First Search

Statement

Given a directed graph represented as an adjacency list, graph, and an integer, source, which is the starting vertex number, return an array of integers, result, that contains the order of the graph’s breadth-first traversal starting from the source vertex.

Constraints:

• $1$ $\leq$graph.length $\leq$$10^3$

• $-1000$ $\leq$graph[i][j] $\leq$$1000$

Solution

To find the breadth-first traversal of a given directed graph, we utilize the breadth-first search (BFS) method, starting from the specified source vertex. This approach ensures that all vertices at the same level (breadth) are visited before proceeding to vertices at the next level. Starting from the source vertex, BFS explores its immediate neighbors first, expanding outward level by level. Unlike tree traversal, graph traversal must account for the possibility of cycles. To manage this, we maintain a record of visited vertices to avoid revisiting them. The process continues until all vertices have been explored, at which point the order of traversal is returned.

We will follow this algorithm to reach the solution:

1. Initialize a queue and an integer array, result to store the order of traversal.

2. Keep track of the visited vertices with the help of visited array. If a vertex has been visited, we mark it as TRUE in the visited array.

3. Enqueue the source vertex, and mark it as visited.

4. Keep on repeating the following steps until the queue is not empty:

   1. Dequeue the vertex, and add it to the result array. Also, check if its neighboring vertices are visited or not.

   2. If they are not visited, enqueue them and mark them as visited.

5. Return the result array, which contains the breadth-first traversal order of the graph starting from the source vertex.

Let’s have a look at the following illustrations for a better understanding of the algorithm above: