Discrete Mathsfor Engineers

7. Applications

BFS is one of the most practical graph algorithms in engineering. Whenever edges represent unit cost (one hop, one move, one step), BFS becomes the default tool.

In this part, we map the theory to real-world tasks you will see in systems, products, and interviews.

7.1 Shortest Paths (Unweighted Graphs)

If each edge has the same “cost” (1 hop), BFS computes shortest-path distances:

And the predecessor pointers π allow path reconstruction (Part 6).

7.2 Grid Pathfinding (Games & Robotics)

A 2D grid can be modeled as a graph:

• Each cell is a vertex
• Edges connect valid neighbor moves (4-neighborhood or 8-neighborhood)
• Walls/obstacles remove vertices or edges

BFS finds the shortest number of moves from start to goal.

7.3 Reachability & Connectivity

BFS answers “can I get there from here?”:

• Run BFS from s
• All discovered vertices are reachable

7.4 Connected Components (Undirected Graphs)

To find all connected components:

1. Mark all vertices as unvisited
2. For each unvisited vertex, run BFS and mark its entire component
3. Each BFS run discovers exactly one component

The total time remains linear:

7.5 Bipartite Checking (Two-Coloring)

BFS can test whether a graph is bipartite by two-coloring layers:

• Assign color A to s
• All neighbors must be color B
• Neighbors of B must be A, and so on
• If an edge connects same-color vertices, the graph is not bipartite

7.6 Levels, Broadcast, and “Degrees of Separation”

BFS naturally computes layers:

This models spreading processes:

• Broadcast message propagation (hops)
• Minimum time steps in discrete diffusion
• “Friends within 2 hops” queries

7.7 Engineering Patterns

BFS is a pattern, not just an algorithm:

• Routing by hop-count: shortest number of hops in overlay networks
• Breadcrumbs / parent pointers: store parents to rebuild paths or UI navigation
• Impact analysis: “what depends on this?” (dependency graphs)
• State-space search: explore transitions in minimal step count