Graphs, BFS, DFS, And Topological Order

Graphs represent entities connected by edges. They may be directed or undirected, weighted or unweighted, cyclic or acyclic.

Why This Matters

Dependencies, workflows, routes, social links, and service relationships are graph problems. Traversal must track visited nodes to terminate on cycles.

Working Model

Breadth-first search explores by distance layers, depth-first search follows one path before backtracking, and topological sorting orders a directed acyclic graph so prerequisites appear first.

Practical Rules

  • Choose an adjacency representation.
  • Track visited or active states.
  • Use BFS for shortest unweighted path.
  • Use DFS for reachability and cycle analysis.
  • Reject cycles before topological scheduling.

Failure Modes

  • Traversing a cyclic graph without visited state.
  • Using BFS for weighted shortest paths.
  • Treating dependency order as unique.
  • Loading an unbounded graph into request memory.

Verification

  • Test disconnected and cyclic graphs.
  • Verify every topological edge points forward.
  • Test multiple valid orders.
  • Bound traversal from external input.

What You Should Be Able To Do

After this lesson, you should be able to explain graph representations, BFS, DFS, cycle detection, and topological dependency ordering, choose a suitable approach for a real PHP project, and verify the result instead of relying on assumptions.

Practice

Practice: Find A Shortest-Hop Path

Find the fewest-link route between two unweighted nodes.

Your answer must:

  • state the intended outcome;
  • show the commands, data flow, or implementation shape;
  • identify at least one unsafe alternative;
  • explain how the result will be verified.
Show solution

Use BFS, record each discovered node's predecessor, stop when the target is discovered, and reconstruct the path backward.

The important part is not memorising one command or vendor screen. The solution makes the invariant, failure behavior, and verification evidence explicit.

Practice: Detect A Dependency Cycle

Detect a cycle in directed package dependencies.

Your answer must:

  • state the intended outcome;
  • show the commands, data flow, or implementation shape;
  • identify at least one unsafe alternative;
  • explain how the result will be verified.
Show solution

Use DFS states for unvisited, active, and complete. An edge to an active node identifies a cycle; retain parents to report the cycle path.

The important part is not memorising one command or vendor screen. The solution makes the invariant, failure behavior, and verification evidence explicit.

Practice: Order Deployments

Topologically order services from declared dependencies.

Your answer must:

  • state the intended outcome;
  • show the commands, data flow, or implementation shape;
  • identify at least one unsafe alternative;
  • explain how the result will be verified.
Show solution

Compute indegrees, queue zero-indegree services, remove outgoing edges, and reject the plan if fewer than all services are emitted.

The important part is not memorising one command or vendor screen. The solution makes the invariant, failure behavior, and verification evidence explicit.