# Breadth First Search (BFS)

## Problem Description

Implement breadth-first search for graph traversal. BFS explores all neighbors at the current depth before moving to nodes at the next depth level.

## What is BFS?

BFS is a graph traversal algorithm that explores all nodes at the present depth before moving to nodes at the next depth level.

## Characteristics

- **Time Complexity**: O(V + E) where V is vertices and E is edges
- **Space Complexity**: O(V) for the queue and visited set
- **Traversal Strategy**: Explore level by level
- **Implementation**: Queue (FIFO)
- **Key Property**: Finds shortest path in unweighted graphs

## How It Works

1. Start at a given node and mark it visited
2. Add it to a queue
3. While queue is not empty:
   - Dequeue a node
   - Visit all unvisited neighbors
   - Mark them visited and enqueue them
4. Repeat until queue is empty

## Your Task

Implement the following methods in `Breadth_First_Search.java`:

1. `bfs(Map<Integer, List<Integer>> graph, int start)` - Basic BFS traversal
2. `shortestPath(Map<Integer, List<Integer>> graph, int start, int end)` - Find shortest path

## Graph Representation

The graph is represented as an adjacency list:
```
Map<Integer, List<Integer>>
Key: vertex
Value: list of adjacent vertices
```

## Test Cases to Consider

- Single node graph
- Path exists between start and end
- No path exists between start and end
- Start equals end
- Disconnected components
- Multiple shortest paths (return any one)

## Hints

- Use a Queue (LinkedList in Java works well)
- Use a Set to track visited nodes
- For shortest path: track parent/predecessor of each node
- Mark nodes as visited when you enqueue them, not when you dequeue

## Applications

- Shortest path in unweighted graphs
- Level order traversal of trees
- Finding connected components
- Web crawling
- Social network connections (friends at distance k)
- GPS navigation

## Follow-up Questions

1. Why does BFS find the shortest path in unweighted graphs?
2. How would you modify BFS for weighted graphs? (Hint: Dijkstra's)
3. How would you find all nodes at distance k from a source?
4. What's the memory trade-off between BFS and DFS?

## BFS vs DFS

| Aspect | BFS | DFS |
|--------|-----|-----|
| Data Structure | Queue | Stack/Recursion |
| Memory | More (stores level) | Less (stores path) |
| Shortest Path | Yes (unweighted) | No |
| Use Case | Level-wise, shortest path | Path finding, cycles |

## Common Pitfalls

- Not marking nodes as visited when enqueueing (causes duplicates)
- Using wrong data structure (Stack instead of Queue)
- Not handling disconnected graphs
- Forgetting to check if start node exists

## Related Algorithms

- Depth First Search (DFS)
- Dijkstra's Algorithm (weighted shortest path)
- A* Search Algorithm
- Bidirectional Search