Breadth First and Depth First Traversal

Here is the graph that has to be traversed:

'''graph representation'''
graph = {1:[2,3], 2:[4,5], 3:[6], 4:None, 5:[7,8], 6:None, 7:None, 8:None}

def breadthFirstTraversal(graph,start):
    visited = []
    tobevisited = [start]
    
    while len(tobevisited) > 0:
        currentNode = tobevisited.pop(0)
        if currentNode not in visited:
            visited += [currentNode]
            if graph[currentNode] is not None:
                tobevisited = tobevisited + graph[currentNode]
                
    return visited


print breadthFirstTraversal(graph,1)

'''Output: [1, 2, 3, 4, 5, 6, 7, 8]'''

def depthFirstTraversal(graph,start):
    visited = []
    tobevisited = [start]
    
    while len(tobevisited) > 0:
        currentNode = tobevisited.pop(0)
        
        if currentNode not in visited:
            visited += [currentNode]
            if graph[currentNode] is not None:
                tobevisited = graph[currentNode] + tobevisited
                
    return visited

print depthFirstTraversal(graph,1)

'''Output: [1, 2, 4, 5, 7, 8, 3, 6]'''

Advertisements