lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

pythonIntroAlgorithms2Chapter3Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter2Title

pythonIntroAlgorithms2Chapter4Title

def bfs(graph, start):
    visited = []
    queue = [start]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            # Use a list to remove duplicates
            queue.extend([n for n in graph[node] if n not in visited])

    return visited

graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}

print(bfs(graph, 'A'))

# Breadth-First Search (BFS) Implementation Guide

## 1. Using a Queue

- BFS uses a queue to manage the nodes that need to be explored. It traverses nodes level by level using the queue.

```python title="Queue Example"
def bfs(graph, start):
    visited = []
    queue = [start]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            # Avoid duplicates using a list
            queue.extend([n for n in graph[node] if n not in visited])

    return visited
```

<br />

## 2. Level-By-Level Traversal

- BFS explores adjacent nodes for each node level by level. This utilizes the FIFO (First In, First Out) property of queues.

```python title="Level-By-Level Traversal Example"
while queue:
    node = queue.pop(0)
    if node not in visited:
        visited.append(node)
        # Avoid duplicates using a list
        queue.extend([n for n in graph[node] if n not in visited])
```

<br />

## Time Complexity

1. `Time Complexity`: (O(V + E))

   - Where `V` is the number of vertices and `E` is the number of edges. Each vertex is visited once, and each edge is checked once.

2. `Shortest Path Search`: BFS is effective in finding the shortest path from the start node to the target node in an undirected graph.

3. `Wide Range Exploration`: BFS effectively explores a wide range of nodes through level-based traversal.