BFT

Breadth first seach. I'm using this really great artical as my primary resource for implementation, and how this works. Basicly the way this works is it starts with some start node, then it goes out to each child node depth first.

With the above visual as an example, I'll walk though what BFS does... we will start at some node of our choosing... in this case I'm going to choose A as the start Node. Then We will procede to go to B. Then we will add B to our visited list, so we cannot hit it again. This is a way to provent cycles from causing infinate loops. Then we will go to D. We will add D to our visited list. Because D does not connect to anything, we will then go to C, because it was pushed on the stack when we started at A. This will not be the exact order, because the set data sturcture that we'll be useing is not orderd as far as I'm aware, but the key idea that we are going deep into the graph first is the idea to take away. This is the primary difference between DFS and BFS (breadth first search)

The biggest key to DFS is how we queue the data for the next iteration. We use a stack in this approche wich has the LIFO (last in first out) property. This property is importent for the order that we treverse the nodes.



In [1]:

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



In [2]:

    
print(graph)









    



{'E': {'B', 'F'}, 'C': {'A', 'F'}, 'A': {'C', 'B'}, 'B': {'E', 'A', 'D'}, 'F': {'E', 'C'}, 'D': {'B'}}



In [3]:

    
set1 = set(['a', 'b'])
set2 = set(['b', 'c'])



In [4]:

    
set1.difference(set2)









    Out[4]:





{'a'}



In [5]:

    
set1.intersection(set2)









    Out[5]:





{'b'}



In [6]:

    
set1.issubset(set2)









    Out[6]:





False



In [7]:

    
set1 = set([1,2,3,4])
set2 = set([2,3,4])



In [8]:

    
set2.issubset(set1)









    Out[8]:





True



In [ ]:



In [13]:

    
graph.values()









    Out[13]:





dict_values([{'B', 'F'}, {'A', 'F'}, {'C', 'B'}, {'E', 'A', 'D'}, {'E', 'C'}, {'B'}])



In [51]:

    
def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        print(vertex)
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited



In [52]:

    
dfs({'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}, 'C')









    



C
F
E
B
D
A
A






    Out[52]:





{'A', 'B', 'C', 'D', 'E', 'F'}

Here is the recursive implementation of DFS:



In [53]:

    
def dfs_rec(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for next in graph[start] - visited:
        dfs_rec(graph, next, visited)
    return visited



In [54]:

    
dfs_rec(graph, 'B')









    Out[54]:





{'A', 'B', 'C', 'D', 'E', 'F'}

DFS Paths:

This is a way to set the possible paths to an end goal node if it exists in the graph



In [6]:

    
def dfs_path(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        (vertex, path) = stack.pop()
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path+[next]
            else:
                stack.append((next, path + [next]))



In [8]:

    
for p in dfs_path(graph, 'A', 'F'):
    print(p)









    



['A', 'C', 'F']
['A', 'B', 'E', 'F']

Breadth First Search or BFS

The big advantage that this approche has over DFS is that you are garenteed to return the shortest path to some node first, which is usually the desired goal for any graph traversal algorithem. The most importent implmentation difference beetween DFS and BFS is that DFS usese a stack which is LIFO where as a BFS uses a queue which is FIFO (first in first out). This order is crutial to the proper algorithem type. The BFS implementation is truly almost the same as the DFS with that little change.



In [11]:

    
def bfs(graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop(0)
        print(vertex)
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(graph[vertex] - visited)
    return visited



In [12]:

    
bfs(graph, 'B')









    



B
E
D
A
F
C
C



In [18]:

    
def bfs_path(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        vertex, path = queue.pop(0)
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path+[next]))



In [21]:

    
for path in bfs_path(graph, 'A', 'C'): # because this is BFS the first result is garenteed to be the shortest path. 
    print(path)









    



['A', 'C']
['A', 'B', 'E', 'F', 'C']



In [ ]: