BFS, DFS and traversal invariants

BFS explores layers using a queue. On unweighted or equal-weight edges, first discovery gives minimum edge count. Mark vertices when enqueuing to avoid repeated queue entries. Parent links reconstruct the path.

DFS follows a branch using a stack or recursion. Discovery/finish times and active-stack colours expose back edges and ordering. In an undirected cycle test, exclude the parent edge; parallel edges may require edge IDs. Recursive depth can reach V.

Restart from every unvisited vertex to cover disconnected graphs. Neighbour order changes traversal order but not correct BFS distances. BFS is not a general weighted shortest-path algorithm; separate edge count from cost.

from collections import deque

def bfs(g, start):
    distance, parent = {start: 0}, {start: None}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in g[u]:
            if v not in distance:
                distance[v], parent[v] = distance[u]+1, u
                q.append(v)
    return distance, parent
assert bfs({"A":["B","C"],"B":["D"],"C":["D"],"D":[]},"A")[0]["D"] == 2