Searching a graph

To find a route through a graph, or everything connected to a starting point, you explore it step by step and remember where you've been, so you don't go round in circles.

Breadth-first search (BFS) explores in rings: first every neighbour of the start, then all of their neighbours, and so on. It keeps a queue of places to visit next. Because it goes ring by ring, the first time it reaches a place is by a route with the fewest edges.

from collections import deque

def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order

g = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": []}
print(bfs(g, "A"))

Depth-first search (DFS) goes as far as it can down one path before backing up to try the next. It uses a stack, or recursion, which uses the call stack. It's natural for solving mazes, checking whether a graph has a cycle, and putting tasks in an order that respects what must come first.

Both visit every vertex and edge once: O(V + E), for V vertices and E edges. When edges have weights (road lengths), the fewest edges isn't the shortest distance; Dijkstra's algorithm handles that, using a priority queue in place of BFS's plain queue.