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