Breadth-First Search (using Python)

Overview

1. Steps
2. Code
3. Time Complexity
4. Conclusion
5. Reference

Steps

1. Add the vertex to start the breadth-first search to the empty queue. Mark that vertex visited.
2. Extract a vertex from the queue and add its neighbors to the queue if that isn’t marked visited.
3. Repeat step 2 until the queue is empty.

Add the vertex to start the breadth-first search to the empty queue. Mark that vertex visited.(從A開始)

Extract a vertex from the queue and add its neighbors to the queue if that isn’t marked visited.

We mark the vertices, B and C as visited because we added these to the queue.

Then we mark vertices D and E visited because we added these to the queue.

We extract vertex C from the queue. However, we don’t have any vertex added to the queue because we’ve already visited all neighbors of vertex C.

We are going to extract vertices D and E, but we’ve also visited these neighbors before. So the queue is empty and we finish to search. Finally, we’ve visited all reachable vertices from vertex A. In other words, we’ve marked all vertices visited.

Code

from collections import deque	


def bfs(graph, vertex):
    queue = deque([vertex])
    
    # The level holds distances from the vertex from which we start searching
    
    level = {vertex: 0}
     # The parent holds the vertex just added as a key 
     # and the vertex from which we reach to the vertex just added as a value
    
    parent = {vertex: None}
    while queue:
        v = queue.popleft()
        # graph[v] returns neighbors of vertex v
        for n in graph[v]:
            if n not in level:            
                queue.append(n)
        
                # we need to increment the i after the for-loop finishes 
                # because we need to expand the circle to search
                
                level[n] = level[v] + 1
                parent[n] = v
    return level, parent

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

print(bfs(graph,'A'))

Output

({'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2} # level
{'A': None, 'B': 'A', 'C': 'A', 'D': 'B', 'E': 'B'}) # parent

Time Complexity

O(|V|+|E|)

vertices: v = queue.popleft()
E is the set of the edges

Conclusion

1. The level holds distances from the vertex from which we start searching.

2. The distance from the vertex to itself is 0, of course, we initialize the level above.

3. The parent holds the vertex just added as a key and the vertex from which we reach to the vertex just added as a value.

Reference

1. Understanding the Breadth-First Search with Python
2. MIT OpenCourseWare 6.006 Lecture 13: Breadth-First Search