Breadth First Search

from collections import deque


def adjacency(pairs, vertices):
    graph = {v: [] for v in vertices}
    for a, b in pairs:
        graph[a].append(b)
        graph[b].append(a)
    for v in graph:
        graph[v].sort()
    return graph


EDGES = [("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"),
         ("C", "F"), ("E", "F"), ("E", "G"), ("F", "H")]
GRAPH = adjacency(EDGES, "ABCDEFGH")


def bfs_levels(graph, start):
    """The same walk, but recording how far each vertex is from the start."""
    level = {start: 0}
    parent = {start: None}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            if w not in level:
                level[w] = level[v] + 1
                parent[w] = v
                queue.append(w)
    return level, parent


level, parent = bfs_levels(GRAPH, "A")

by_level = {}
for v, d in level.items():
    by_level.setdefault(d, []).append(v)

print("distance from A, in edges:")
for d in sorted(by_level):
    print("   level %d : %s" % (d, " ".join(sorted(by_level[d]))))
print()
print("every vertex, with its distance and the vertex it was found from:")
for v in sorted(level):
    print("   %s  distance %d  found from %s" % (v, level[v], parent[v] or "(start)"))
print()


def path_to(parent, v):
    steps = []
    while v is not None:
        steps.append(v)
        v = parent[v]
    return list(reversed(steps))


for target in ("H", "G", "D"):
    route = path_to(parent, target)
    print("shortest route A to %s : %s  (%d edges)"
          % (target, " -> ".join(route), len(route) - 1))

from collections import deque

GRAPH = {"A": ["B"], "B": ["A", "C"], "C": ["B"]}      # a path with a cycle in it

print("the same walk with NO visited set, capped at 40 steps so it can finish:")
queue = deque(["A"])
order = []
CAP = 40
while queue and len(order) < CAP:
    v = queue.popleft()
    order.append(v)
    for w in GRAPH[v]:
        queue.append(w)

print("   first 20 vertices reported:", " ".join(order[:20]))
print("   it reported %d vertices from a graph of %d" % (len(order), len(GRAPH)))
print("   the queue is still not empty:", len(queue) > 0)
print("   so it hit the cap rather than finishing:", len(order) == CAP)
print()
print("A and B are joined both ways, so each one keeps re-enqueueing the other.")
print("the visited set is not an optimisation. it is what makes BFS terminate.")

from collections import deque


def ring_with_chords(n):
    graph = {i: [] for i in range(n)}
    pairs = set()
    for i in range(n):
        for j in ((i + 1) % n, (i * 7 + 3) % n):
            if i != j:
                pairs.add((min(i, j), max(i, j)))
    for a, b in sorted(pairs):
        graph[a].append(b)
        graph[b].append(a)
    return graph, len(pairs)


def bfs_list(graph, start):
    visited = {start}
    queue = deque([start])
    reads = 0
    while queue:
        v = queue.popleft()
        for w in graph[v]:
            reads += 1
            if w not in visited:
                visited.add(w)
                queue.append(w)
    return len(visited), reads


def bfs_matrix(matrix, start):
    n = len(matrix)
    visited = {start}
    queue = deque([start])
    reads = 0
    while queue:
        v = queue.popleft()
        for w in range(n):
            reads += 1
            if matrix[v][w] and w not in visited:
                visited.add(w)
                queue.append(w)
    return len(visited), reads


print("%8s %8s %14s %16s %16s"
      % ("vertices", "edges", "list reads", "2E", "matrix reads"))
for n in (10, 100, 1000):
    graph, e = ring_with_chords(n)
    matrix = [[0] * n for _ in range(n)]
    for v, ns in graph.items():
        for w in ns:
            matrix[v][w] = 1
    seen_l, reads_l = bfs_list(graph, 0)
    seen_m, reads_m = bfs_matrix(matrix, 0)
    print("%8d %8d %14d %16d %16d" % (n, e, reads_l, 2 * e, reads_m))
    assert seen_l == seen_m == n, "both must reach every vertex"

print()
print("the list reads exactly 2E entries. the matrix reads V squared cells.")
print("same algorithm, same answer, O(V + E) against O(V squared).")