BFS in Graph

Easy
0/40
Average time to solve is 10m
profile
Contributed by
250 upvotes
Asked in companies
DelhiverySAP LabsCognizant

Problem statement

Given an adjacency list representation of a directed graph with ‘n’ vertices and ‘m’ edges. Your task is to return a list consisting of Breadth-First Traversal (BFS) starting from vertex 0.


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

example

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
8 7
0 1
0 2
0 3
1 4
1 7
2 5
3 6
Sample Output 1:
0 1 2 3 4 7 5 6
Explanation for sample input 1:

example

n = 8: There are 8 vertices in the graph, labeled from 0 to 7.
m = 7: There are 7 directed edges in the graph.

The directed edges are as follows:
Vertex 0 has directed edges towards vertices 1, 2, and 3.
Vertex 1 has directed edges towards vertices 4 and 7.
Vertex 2 has a directed edge towards vertex 5.
Vertex 3 has a directed edge towards vertex 6.
Vertices 4, 5, 6, and 7 have no outgoing edges.

Adjacency list: {{1,2,3}, {4,7}, {5}, {6}, {}, {}, {}, {}}. This is passed to the bfsTraversal function.
Sample Input 2:
4 4
0 1
0 2
1 2
0 3
Sample Output 2:
0 1 2 3
Constraints :
1 <= 'n', 'm' <= 10^4

Where 'n' is the number of vertices and 'm' is the number of edges.

Time Limit: 1 second
Hint

Try to use a queue to maintain the order of vertices to be visited.

Approaches (1)
Using queue

Approach:

The approach for Breadth-First Traversal (BFS) of a directed graph starting from vertex 0 is to use a queue to maintain the order of vertex exploration. We start by enqueuing vertex 0 and marking it as visited. Then, while the queue is not empty, we dequeue the front vertex, add it to the result array, and explore its neighbors. For each unvisited neighbor, we mark it as visited and enqueue it. This process continues until the queue becomes empty. The result array will contain the vertices visited in BFS order.

 

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.
Time Complexity

O(n + m), where ‘n’ is the number of vertices and ‘m’ is the number of edges in the input graph.

 

The BFS algorithm visits each vertex and each edge in the graph once during the traversal process. For each vertex, it examines its neighbors (edges) and enqueues them in the queue. This process takes O(n) time for visiting all 'n' vertices and O(m) time for visiting all 'm' edges. 

Space Complexity

O(n), where ‘n’ is the number of vertices.

 

Space utilization:

Queue: The queue data structure is used to store vertices during the traversal. At most, it can contain all n vertices if the graph is connected and there are no isolated vertices. Therefore, the space complexity of the queue is O(n).

Visited Array: An array of size n is used to keep track of visited vertices. Each element in the array represents a vertex, and it requires constant space for each vertex. Hence, the space complexity of the visited array is O(n).

Output Vector: The result vector that stores the BFS traversal order contains at most n vertices, which again contributes to a space complexity of O(n).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
BFS in Graph
Full screen
Console