--- Difficulty: Easy Source: 160 Days of Problem Solving Tags: - Graph - BFS --- # πŸš€ _Day 2. BFS of Graph_ 🧠 The problem can be found at the following link: [Question Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/graph-gfg-160/problem/bfs-traversal-of-graph) ## πŸ’‘ **Problem Description:** Given a **connected undirected graph** represented by a **2D adjacency list `adj[][]`**, where `adj[i]` represents the list of vertices connected to vertex `i`. Perform a **Breadth First Search (BFS) traversal** starting from **vertex 0**, visiting vertices from left to right as per the given adjacency list. Return a list containing the **BFS traversal** of the graph. **Note:** Traverse nodes in the same order as given in the adjacency list. > Note: Sorry for uploading late, my exam is going on. ## πŸ” **Example Walkthrough:** ### **Example 1:** #### **Input:** ``` adj = [[1, 2, 3], [0], [0, 4], [0], [2]] ``` #### **Output:** ``` [0, 1, 2, 3, 4] ``` #### **Explanation:** Starting from vertex **0**: - Visit **0** β†’ Output: `[0]` - Visit **2** (first neighbor of 0) β†’ Output: `[0, 2]` - Visit **3** (next neighbor of 0) β†’ Output: `[0, 2, 3]` - Visit **1** (next neighbor of 0) β†’ Output: `[0, 2, 3]` - Visit **4** (neighbor of 2) β†’ Final Output: `[0, 2, 3, 1, 4]` ### **Example 2:** #### **Input:** ``` adj = [[1, 2], [0, 3], [0, 3, 4], [1, 2], [2]] ``` #### **Output:** ``` [0, 1, 2, 3, 4] ``` #### **Explanation:** Starting from vertex **0**: - Visit **0** β†’ Output: `[0]` - Visit **1** (first neighbor of 0) β†’ Output: `[0, 1]` - Visit **2** (next neighbor of 0) β†’ Output: `[0, 1, 2]` - Visit **3** (first unvisited neighbor of 2) β†’ Output: `[0, 1, 2, 3]` - Visit **4** (next neighbor of 2) β†’ Final Output: `[0, 1, 2, 3, 4]` ## **Constraints:** - $1 \leq$ `adj.size()` $\leq 10^4$ - $1 \leq$ `adj[i][j]` $\leq 10^4$ ## 🎯 **My Approach:** ### **Iterative BFS (Using Queue)** ### **Algorithm Steps:** 1. Maintain a **visited array** to track visited nodes. 2. Use a **queue** to process nodes in a FIFO manner. 3. Start BFS traversal from node `0` and enqueue it. 4. Process nodes from the queue and visit their unvisited neighbors in order. 5. Store the **BFS traversal sequence** in a list. ## πŸ•’ **Time and Auxiliary Space Complexity** - **Expected Time Complexity:** O(V + E), since each vertex and edge is visited once. - **Expected Auxiliary Space Complexity:** O(V), as we store the visited array and queue. ## πŸ“ **Solution Code** ## **Code (C++)** ```cpp class Solution { public: vector bfs(vector>& adj) { int V = adj.size(); vector res; vector vis(V, false); queue q; q.push(0); vis[0] = true; while (!q.empty()) { int v = q.front(); q.pop(); res.push_back(v); for (int u : adj[v]) { if (!vis[u]) { vis[u] = true; q.push(u); } } } return res; } }; ```

⚑ Alternative Approaches

 ## πŸ“Š **2️⃣ Recursive BFS Approach** #### **Algorithm Steps:** 1. Use a helper function for recursion. 2. Process the front element of the queue. 3. Enqueue unvisited neighbors and call the function recursively. ```cpp class Solution { public: void bfsUtil(queue& q, vector>& adj, vector& res, vector& vis) { if (q.empty()) return; int v = q.front(); q.pop(); res.push_back(v); for (int u : adj[v]) { if (!vis[u]) { vis[u] = true; q.push(u); } } bfsUtil(q, adj, res, vis); } vector bfs(vector>& adj) { vector res; vector vis(adj.size(), false); queue q; q.push(0); vis[0] = true; bfsUtil(q, adj, res, vis); return res; } }; ``` #### πŸ“ **Complexity Analysis:** - βœ… **Time Complexity:** O(V + E) - Each vertex and edge are processed once. - βœ… **Space Complexity:** O(V) - Due to the recursion stack. #### βœ… **Why This Approach?** - Uses recursion instead of iteration, which may be preferred in some functional programming paradigms. - However, recursion depth could lead to **stack overflow for large graphs**. ## πŸ”„ **3️⃣ BFS for Disconnected Graphs** #### **Algorithm Steps:** 1. Iterate through all vertices to ensure that all components are covered. 2. If a vertex is not visited, initiate BFS from it. 3. This ensures traversal of all disconnected components. ```cpp class Solution { public: vector bfs(vector>& adj) { int V = adj.size(); vector res; vector vis(V, false); for (int i = 0; i < V; i++) { if (!vis[i]) { queue q; q.push(i); vis[i] = true; while (!q.empty()) { int v = q.front(); q.pop(); res.push_back(v); for (int u : adj[v]) { if (!vis[u]) { vis[u] = true; q.push(u); } } } } } return res; } }; ``` #### πŸ“ **Complexity Analysis:** - βœ… **Time Complexity:** O(V + E) - Each vertex and edge are processed once. - βœ… **Space Complexity:** O(V) - Due to the queue and visited array. #### βœ… **Why This Approach?** - **Handles disconnected graphs**, ensuring all components are explored. - Slightly more complex than basic BFS but necessary for completeness. ## πŸ“Š **4️⃣ BFS Using Deque (Optimized Queue Handling)** #### **Algorithm Steps:** 1. Instead of `queue`, we use `deque` for optimized front and back operations. 2. The traversal logic remains the same as the standard BFS approach. ```cpp class Solution { public: vector bfs(vector>& adj) { int V = adj.size(); vector res; vector vis(V, 0); deque q; vis[0] = 1; q.push_back(0); while (!q.empty()) { int v = q.front(); q.pop_front(); res.push_back(v); for (int u : adj[v]) { if (!vis[u]) { vis[u] = 1; q.push_back(u); } } } return res; } }; ``` #### πŸ“ **Complexity Analysis:** - βœ… **Time Complexity:** O(V + E) - Each vertex and edge are processed once. - βœ… **Space Complexity:** O(V) - Due to the deque and visited array. #### βœ… **Why This Approach?** - Using a `deque` can slightly **improve performance** in some cases due to optimized operations compared to `queue`. - Useful when frequent push/pop operations from both ends are required. ### πŸ†š **Comparison of Approaches** | **Approach** | ⏱️ **Time Complexity** | πŸ—‚οΈ **Space Complexity** | βœ… **Pros** | ⚠️ **Cons** | | ------------------------------- | ---------------------- | ----------------------- | ----------------------------------- | --------------------------------------- | | **Standard BFS (Queue)** | 🟒 O(V + E) | 🟑 O(V) | Simple and widely used | Fails for disconnected graphs | | **Recursive BFS** | 🟒 O(V + E) | 🟑 O(V) | Recursive and intuitive | Risk of stack overflow for large graphs | | **BFS for Disconnected Graphs** | 🟒 O(V + E) | 🟑 O(V) | Ensures traversal of all components | Slightly more complex than basic BFS | | **BFS Using (Deque)** | 🟒 O(V + E) | 🟑 O(V) | Optimized performance using `deque` | Marginal improvement over normal queue | βœ… **Best Choice?** - **Use Standard BFS** if the graph is **connected** and efficiency is the priority. - **Use BFS for Disconnected Graphs** when handling **multiple components**. - **Use Recursive BFS** only if recursion depth is not an issue. - **Use Deque BFS** if frequent front and back operations are needed.
## **Code (Java)** ```java class Solution { public ArrayList bfs(ArrayList> adj) { ArrayList r = new ArrayList<>(); boolean[] v = new boolean[adj.size()]; Queue q = new LinkedList<>(); q.add(0); v[0] = true; while (!q.isEmpty()) { int i = q.poll(); r.add(i); for (int j : adj.get(i)) { if (!v[j]) { v[j] = true; q.add(j); } } } return r; } } ``` ## **Code (Python)** ```python from collections import deque class Solution: def bfs(self, adj): r, v = [], [False] * len(adj) q = deque([0]) v[0] = True while q: i = q.popleft() r.append(i) for j in adj[i]: if not v[j]: v[j] = True q.append(j) return r ``` ## 🎯 **Contribution and Support:** For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative! ⭐ **If you find this helpful, please give this repository a star!** ⭐ ---

πŸ“Visitor Count