Breadth-First and Depth-First Search

from collections import deque

def search(graph, start, use_bfs=True):
    frontier = deque([start])
    seen = {start}
    order = []

    while frontier:
        vertex = frontier.popleft() if use_bfs else frontier.pop()
        #                  ↑ oldest              ↑ newest
        #        THIS IS THE ONLY DIFFERENCE
        order.append(vertex)

        for neighbour in graph[vertex]:
            if neighbour not in seen:
                seen.add(neighbour)          # mark on DISCOVERY, not on visit
                frontier.append(neighbour)

    return order

# WRONG — mark when popped
while frontier:
    v = frontier.popleft()
    if v in seen:
        continue
    seen.add(v)
    for n in graph[v]:
        frontier.append(n)       # n may already be waiting, several times over

# In a dense graph a vertex can be pushed once per incoming edge. The
# frontier bloats to O(E) and the algorithm does far more work than it
# needs to — still correct, but slow and memory-hungry.


# RIGHT — mark on discovery
while frontier:
    v = frontier.popleft()
    for n in graph[v]:
        if n not in seen:
            seen.add(n)          # ← immediately, before it goes on the frontier
            frontier.append(n)

# Each vertex enters the frontier at most once. O(V) memory, O(V + E) time.

from collections import deque

def shortest_path(graph, start, goal):
    """Fewest edges from start to goal, as a list of vertices."""
    if start == goal:
        return [start]

    parent = {start: None}          # also serves as the visited set
    q = deque([start])

    while q:
        v = q.popleft()
        for n in graph[v]:
            if n not in parent:
                parent[n] = v       # remember HOW we got here
                if n == goal:
                    return rebuild(parent, goal)
                q.append(n)
    return None                     # unreachable


def rebuild(parent, goal):
    """Walk the parent pointers backwards, then reverse."""
    path = []
    while goal is not None:
        path.append(goal)
        goal = parent[goal]
    return path[::-1]

def distances(graph, start):
    dist = {start: 0}
    q = deque([start])
    while q:
        v = q.popleft()
        for n in graph[v]:
            if n not in dist:
                dist[n] = dist[v] + 1
                q.append(n)
    return dist            # anything missing is unreachable

def levels(graph, start):
    seen = {start}
    frontier = [start]
    depth = 0
    while frontier:
        print(f"distance {depth}: {frontier}")
        nxt = []
        for v in frontier:                    # everything at THIS distance
            for n in graph[v]:
                if n not in seen:
                    seen.add(n)
                    nxt.append(n)
        frontier = nxt
        depth += 1

def dfs(graph, v, seen=None):
    if seen is None:
        seen = set()
    seen.add(v)
    process(v)                       # PRE-order: on the way down
    for n in graph[v]:
        if n not in seen:
            dfs(graph, n, seen)
    finish(v)                        # POST-order: on the way back up
    return seen

# The iterative version, for graphs deeper than ~1000:
def dfs_iterative(graph, start):
    stack = [start]
    seen = set()
    while stack:
        v = stack.pop()
        if v in seen:
            continue
        seen.add(v)
        process(v)
        for n in reversed(graph[v]):   # reversed → same order as recursion
            if n not in seen:
                stack.append(n)

WHITE, GREY, BLACK = 0, 1, 2      # unseen / in progress / finished

def has_cycle(graph):
    colour = {v: WHITE for v in graph}

    def visit(v):
        colour[v] = GREY                    # on the current path
        for n in graph[v]:
            if colour[n] == GREY:
                return True                 # ← back edge: a cycle
            if colour[n] == WHITE and visit(n):
                return True
        colour[v] = BLACK                   # done, and off the path
        return False

    return any(colour[v] == WHITE and visit(v) for v in graph)

# GREY means A. Reaching a GREY vertex means
# you have looped back onto your own path.
#
# A BLACK vertex is fine to meet again — it just means two different paths
# reach the same finished region.

# Counting islands — the pattern for every A problem
def count_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen = set()
    count = 0

    def flood(r, c):
        stack = [(r, c)]
        while stack:
            cr, cc = stack.pop()
            if (cr, cc) in seen:
                continue
            seen.add((cr, cc))
            for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
                nr, nc = cr + dr, cc + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and grid[nr][nc] == "1" and (nr, nc) not in seen):
                    stack.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                count += 1        # a new island
                flood(r, c)       # absorb all of it
    return count

# Same shape as counting connected components in Chapter 19 — because
# that is exactly what it is.