Question 3 of 7: Graph Traversal and Spanning Trees

Question 3: Graph Traversal and Spanning Trees (20 marks: 4 items, 5 marks each)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Part (a) — Depth First Search (5 marks). DFS explores a graph by going as deep as possible along one branch before backtracking: from the current vertex it picks an unvisited neighbour, moves to it, and recurses, only returning to try a different neighbour once every path forward from the current vertex has been exhausted. It is naturally implemented with an explicit stack or with recursion (the call stack playing the same role), and it visits every vertex reachable from the start exactly once, in $O(V+E)$ time using an adjacency-list representation.

Part (b) — Breadth First Search (5 marks). BFS explores a graph level by level: it visits the start vertex, then all of its immediate neighbours, then all of their unvisited neighbours, and so on, using a FIFO queue to keep track of the frontier rather than a stack. Because it expands outward one "ring" of distance at a time, BFS is the algorithm of choice whenever the shortest path in terms of number of edges is wanted, and it also runs in $O(V+E)$ time.

Part (c) — Relation to spanning trees (5 marks). Running either DFS or BFS from a start vertex on a connected graph and recording only the edges used to discover a new (previously unvisited) vertex — discarding every edge that leads to an already-visited vertex — produces a spanning tree of the graph: every vertex is reached, no cycles are created (because a revisit edge is always dropped), and exactly $|V|-1$ edges are kept. The two traversals give different trees on the same graph (a DFS tree tends to be tall and stringy, a BFS tree short and bushy), but both are valid spanning trees; neither is generally a minimum-weight spanning tree unless edge weights happen to align with traversal order.

Part (d) — Kruskal's algorithm (5 marks). Kruskal's algorithm sorts all edges of the graph by non-decreasing weight and processes them in that order, adding an edge to the growing forest only if its two endpoints currently lie in different components (i.e. adding it would not close a cycle); an edge that would close a cycle is skipped. A disjoint-set (union–find) structure tracks components efficiently. The process stops once $|V|-1$ edges have been accepted, at which point the forest is a single spanning tree, and the cut property (the lightest edge crossing any cut belongs to some minimum spanning tree) guarantees it is minimum.

In practice the choice between DFS, BFS and Kruskal is driven by what the traversal needs to answer, not just by which tree it happens to produce. DFS is the natural fit for exhaustive search tasks such as maze-solving, topological sorting, or finding connected components, because its stack-like behaviour costs nothing extra to implement recursively. BFS is preferred whenever "fewest hops" matters — unweighted shortest-path queries, web-crawler frontier expansion, or level-order network broadcasts — precisely because it explores in strict distance order. Kruskal (or Prim) is reserved for problems that are explicitly about minimizing total edge cost, such as designing a low-cost cable or road network that connects every site; running a plain traversal on the same graph would connect every vertex correctly but could easily cost far more than necessary, since traversal order has no relationship to edge weight.