Solution: Implement Breadth-First Search
Let’s solve the Breadth-First Search problem.
We'll cover the following
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:
graph.length
graph[i][j]
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:
Initialize a
queue
and an integer array,result
to store the order of traversal.Keep track of the visited vertices with the help of
visited
array. If a vertex has been visited, we mark it as TRUE in thevisited
array.Enqueue the
source
vertex, and mark it as visited.Keep on repeating the following steps until the
queue
is not empty:Dequeue the vertex, and add it to the
result
array. Also, check if its neighboring vertices are visited or not.If they are not visited, enqueue them and mark them as visited.
Return the
result
array, which contains the breadth-first traversal order of the graph starting from thesource
vertex.
Let’s have a look at the following illustrations for a better understanding of the algorithm above:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.