# minte9 LearnRemember

### 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

visited.append(v.value)

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: 355 days ago