minte9
LearnRemember





Click to Flip Card

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?

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