---

📘 Breadth-First Search (BFS)

1️⃣ Introduction

Breadth-First Search (BFS) is a fundamental graph traversal algorithm.

🔹 Definition

BFS explores a graph level by level, visiting all neighbors of a node before moving to the next level.

It uses a queue (FIFO) data structure.

---

2️⃣ Key Idea of BFS

• Start from a source node
• Visit all its adjacent nodes
• Then visit nodes at the next level
• Continue until all reachable nodes are visited

---

3️⃣ Working Principle

🔹 Steps

1. Start from a source vertex
2. Mark it as visited
3. Insert it into a queue
4. While queue is not empty:
   • Remove front node
   • Visit all its unvisited neighbors
   • Mark them visited and enqueue

---

4️⃣ Algorithm (BFS)

🔹 Pseudocode

BFS(G, s):
   create queue Q
   mark s as visited
   enqueue(Q, s)

   while Q is not empty:
       u = dequeue(Q)
       print u

       for each vertex v adjacent to u:
           if v is not visited:
               mark v as visited
               enqueue(Q, v)

---

5️⃣ Example

🔹 Graph:

      A
     / \
    B   C
   / \   \
  D   E   F

---

🔹 BFS Traversal (Starting from A)

A → B → C → D → E → F

✔ Level-wise traversal

---

6️⃣ Queue Operation Trace

Step	Queue	Output
Start	[A]	A
Visit A	[B, C]	A
Visit B	[C, D, E]	A B
Visit C	[D, E, F]	A B C
Visit D	[E, F]	A B C D
Visit E	[F]	A B C D E
Visit F	[]	A B C D E F

---

7️⃣ Time Complexity

🔹 Using Adjacency List

[
O(V + E)
]

Where:

• V = number of vertices
• E = number of edges

---

🔹 Using Adjacency Matrix

[
O(V^2)
]

---

8️⃣ Space Complexity

• Queue: O(V)
• Visited array: O(V)

---

9️⃣ Characteristics of BFS

✔ Level-order traversal
✔ Uses queue (FIFO)
✔ Finds shortest path in unweighted graph
✔ Complete traversal

---

🔟 Applications of BFS

• Shortest path in unweighted graphs
• Web crawling
• Social networks (friend suggestions)
• GPS navigation
• Broadcasting in networks

---

1️⃣1️⃣ Advantages

✔ Simple and easy to implement
✔ Guarantees shortest path (unweighted graph)
✔ Works for both directed and undirected graphs

---

1️⃣2️⃣ Disadvantages

✖ Requires more memory (queue)
✖ Not suitable for deep graphs
✖ Slower than DFS in some cases

---

1️⃣3️⃣ BFS vs DFS

Feature	BFS	DFS
Data Structure	Queue	Stack
Traversal	Level-wise	Depth-wise
Shortest Path	Yes	No
Memory	More	Less

---

🔚 Conclusion

Breadth-First Search is a fundamental graph traversal technique that explores nodes level by level and is widely used for finding shortest paths in unweighted graphs.

BFS guarantees the shortest path in unweighted graphs due to its level-order traversal.

---

📌 Exam Tip

👉 Always include:

• Queue-based approach
• Algorithm
• Example traversal
• Time complexity

---