breadth first search graph

# returns a list with elements in order of the path
# between the start and end of a graph
# @param parent dict the mapping between node and parent
# @param start int the starting node
# @param end int the ending node
def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path

# Does a breadth first search of a graph
# @param graph list of lists, adjacency list
# @param source int the source node to start the search
# @param target int the target node to search for
def bfs(graph, source, target):
    queue = []
    visited = {}
    parent = {}
    
    for node in xrange(len(graph)):
        visited[node] = False
        parent[node] = None
    
    queue.append(source)
    while len(queue) != 0:
        current = queue.pop(0)
        if current == target:
            print backtrace(parent, source, target)
            break
        for neighbor in graph[current]:
            if visited[neighbor] == False:
            	visited[neighbor] = True
                parent[neighbor] = current
            	queue.append(neighbor)
    print visited
    print parent
    print target
        
    
adjList = [
    [1],
    [0, 4, 5],
    [3, 4, 5],
    [2, 6],
    [1, 2],
    [1, 2, 6],
    [3, 5],
    []
    ];

bfs(adjList, 2, 1)

Browser Version Not Supported

Due to Python Fiddle's reliance on advanced JavaScript techniques, older browsers might have problems running it correctly. Please download the latest version of your favourite browser.
Chrome 10+ Firefox 4+ Safari 5+
IE 10+

Let me try anyway!

Python Fiddle

Python Cloud IDE