Breadth-First and Depth-First Search

Breadth-first search starts from a vertex and processes pending vertices using a FIFO queue. Newly discovered neighbours are added to the rear, so vertices reached through fewer edges are processed before more distant vertices. Record a vertex as discovered when enqueuing it to avoid adding it repeatedly.

In an unweighted graph, BFS can find a shortest path measured by number of edges. Store a predecessor when each vertex is first discovered to reconstruct a route. This guarantee does not mean BFS minimises arbitrary weighted costs.

Depth-first search follows a branch as far as possible before backtracking. Recursive calls naturally retain unfinished branches on a call stack; an explicit stack can implement similar behaviour. A visited set prevents cycles from causing repeated exploration.

Traversal order is not unique unless the neighbour rule is stated. An explicit stack may need neighbours pushed in reverse order to reproduce a chosen recursive alphabetical order. DFS can explore maze connectivity, but its first route to a destination need not be the shortest.

With adjacency lists and suitable visited tracking, both traversals visit each reachable vertex and examine its relevant edges, giving O(V+E) work for the traversed graph. An adjacency matrix changes the neighbour-inspection cost because every possible neighbour may need checking.

A traversal started at one vertex does not visit disconnected components automatically. Repeat from an unvisited vertex if the task requires the whole graph. Distinguish visiting order, discovery order and the route reconstructed from predecessor links; they are related but not identical outputs.

from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
queue = deque(["A"])
seen = {"A"}
order = []
while queue:
    node = queue.popleft()
    order.append(node)
    for neighbour in graph[node]:
        if neighbour not in seen:
            seen.add(neighbour)
            queue.append(neighbour)
print(order)

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.