Breadth First Search
Which data structure uses BFS for traverse? When we want to stay close to the starting point, what do we use? When we want to move far away quickly, what do we use?
![](/lib/images/knowledge_graph.png)
BFS Traversal
Unlike DFS, Breadth First Search doesn't use recursion, it uses queue. We can start at any vertex and run the loop until the queue is empty.
from collections import deque
def bfs_traverse(starting_vertex):
queue = deque()
visited = []
visited.append(starting_vertex.value)
# Add starting vertex to the queue
queue.append(starting_vertex)
# While queue is not empty
while bool(queue) == True:
# Remove the first vertex and make it the current vertex
current_vertex = queue.popleft()
# Iterate over adjacent vertices
for v in current_vertex.adjacent_vertices:
if v.value in visited:
continue
# Add adjacent vertex to visited
visited.append(v.value)
# Add adjacent vertex to queue
queue.append(v)
return visited
print([x for x in bfs_traverse(a)])
print([x for x in bfs_traverse(f)])
"""
['Alice', 'Bob', 'Candy', 'Derek', 'Elaine', 'Fred', 'Helen', 'Gina', 'Irena']
['Fred', 'Bob', 'Helen', 'Alice', 'Candy', 'Derek', 'Elaine', 'Gina', 'Irena']
"""
DFS vs BFS
When we want to move far away quickly, we use DFS. When we want to stay close to the starting point, we use BFS.
def dfs_traverse2(vertex, visited=None, level=0):
if visited is None:
visited = []
if level == 2:
return visited # Look Here
if level > 0:
visited.append(vertex.value)
for v in vertex.adjacent_vertices:
if v.value in visited:
continue
dfs_traverse2(v, visited, level+1) # recusion
return visited
print('Alice\'s direct friends:', [x for x in dfs_traverse2(a)])
print('Helen\'s direct friends:', [x for x in dfs_traverse2(h)])
"""
Alice's direct friends: ['Bob', 'Candy', 'Derek', 'Elaine']
Helen's direct friends: ['Candy', 'Fred']
"""
Last update: 344 days ago