Graphs, BFS, and DFS for dependency questions

Give every edge one meaning

For this exercise, A -> B means B could be affected if A becomes unavailable. The small graph below is a teaching model inspired by the application. It does not discover MicroBank’s full architecture automatically. An Accounts database failure can affect Accounts; whether a user journey fails also depends on retries, queues, caches, and which operation was attempted.

Breadth-first search (BFS) uses a queue and finds minimum edge counts from a starting point in an unweighted graph. Depth-first search (DFS) follows branches using a stack. Neither discovers incident causality from a diagram alone. Reversing all edges answers a different question.

Traverse a small model

Save as graph_walk.py. Every vertex must be a key, including vertices with no outgoing edges.

from collections import deque


def validate(graph, start):
    if start not in graph:
        raise ValueError("Unknown starting vertex")
    if any(v not in graph for edges in graph.values() for v in edges):
        raise ValueError("Every referenced vertex must be declared")


def bfs_distances(graph, start):
    validate(graph, start)
    distance = {start: 0}
    queue = deque([start])
    while queue:
        current = queue.popleft()
        for neighbour in graph[current]:
            if neighbour not in distance:
                distance[neighbour] = distance[current] + 1
                queue.append(neighbour)
    return distance


def dfs_reachable(graph, start):
    validate(graph, start)
    seen = {start}
    stack = [start]
    while stack:
        current = stack.pop()
        for neighbour in graph[current]:
            if neighbour not in seen:
                seen.add(neighbour)
                stack.append(neighbour)
    return seen


impact = {
    "accounts-db": ["accounts"],
    "accounts": ["deposit-journey"],
    "ledger-db": ["ledger"],
    "ledger": ["deposit-journey"],
    "deposit-journey": [],
}
assert bfs_distances(impact, "accounts-db") == {
    "accounts-db": 0, "accounts": 1, "deposit-journey": 2,
}
assert dfs_reachable(impact, "accounts-db") == {
    "accounts-db", "accounts", "deposit-journey",
}

With adjacency lists, validation and traversal take O(V + E) work; the extra queue/stack and visited structure use O(V) space. A visited marker prevents repeated expansion in a cycle. It does not identify whether a directed cycle exists: directed cycle detection needs additional state, such as an active DFS path or the indegree method in the next bite.

Follow the queue and stack

For BFS starting at accounts-db, the queue first contains only that vertex at distance zero. Removing it discovers accounts at distance one. Removing accounts discovers deposit-journey at distance two. A second route to an already discovered vertex does not enqueue it again. Marking it when enqueued avoids duplicate pending work and preserves the first minimum-hop distance.

Run python3 graph_walk.py in the exercise directory, then add a disconnected vertex metrics: [] to the fixture. It should not appear in the result from accounts-db. Add a self-loop to the starting vertex in a scratch copy: visited tracking still stops repeated expansion. Returning successfully does not mean the graph is acyclic; the next bite answers that different question.

Practise boundaries

Test a disconnected vertex, a self-loop, two routes to one vertex, and an unknown neighbour. A shortest hop count is not the lowest-latency network path when edges have different weights. During an incident, use this graph to guide investigation; reachability alone is not a reason to restart a service.

Checkpoint and revision

Draw the edge direction before running either function. Explain why BFS marks a vertex when enqueuing it. For an observed Accounts error, list what logs, timestamps, and request evidence you would need before calling the database the cause.

Checkpoint answer: graph distance is a count of edges under this declared model, not measured network latency. To blame the database for an Accounts error, correlate the failing request with the actual database target, error/wait, and time window. Keep the graph as an investigation map while testing the hypothesis.

Sources

MIT BFS↗, MIT DFS↗, and Python deque↗.