Python - Graph Data Structure - How Do I Implement Breadth-First Search to Find Reachable Vertices Correctly

Your code is way too complicated.

Start with a code just implementing the fundamentals and add features gradually. In order to get you started I'll post something simple but fundamental when handling graphs.

from collections import deque

class fringe(object):
    def __init__(self, kind= 'stack'):
        f= deque()
        self._p= f.append if kind is 'stack' else f.appendleft
        self._f= f

    def __call__(self, item):
        self._p(item)
        return self

    def __iter__(self):
        while len(self._f):
            item= self._f.pop()
            yield item

    def __repr__(self):
        return self._f.__repr__().replace('deque', 'fringe')

def paths(G, start, terminal, F= fringe()):
    for node, path in F((start, [start])):
        for node in G[node]:
            if node is terminal:
                yield path+ [terminal]
            elif node not in path:
                F((node, path+ [node]))

and a test:

if __name__ == '__main__':
    a, b, c, d, e, f= 'A', 'B', 'C', 'D', 'E', 'F'
    G= {a: [b, c], b: [c, d], c: [d], d: [c], e: [f], f: [c]}
    print 'All paths from:', a, 'to:', d
    print 'BFS'
    for path in paths(G, a, d): print path
    print 'DFS'
    for path in paths(G, a, d, fringe('queue')): print path

run will produce:

All paths from: A to: D
BFS
['A', 'C', 'D']
['A', 'B', 'D']
['A', 'B', 'C', 'D']
DFS
['A', 'B', 'D']
['A', 'C', 'D']
['A', 'B', 'C', 'D']