Graph & Tree Algorithms
BFS, DFS, tree traversals, Dijkstra's, topological sort — vocabulary for technical discussions
Graph & tree vocabulary
- BFS — breadth-first (queue); finds shortest path by hops; level-by-level
- DFS — depth-first (stack/recursion); cycle detection; pre/in/post-order traversal
- In-order — left→node→right; produces sorted output on a BST
- Dijkstra's — shortest path by total edge weight; requires non-negative weights
- Topological sort — DAG ordering; each node before its dependents (build systems, task queues)
Question 0 of 5
In a code review, a comment says: "This uses BFS to find the shortest path." What does BFS stand for and how does it work?
Breadth-First Search: explore all nodes at distance 1, then distance 2, etc., using a queue. BFS vocabulary:
- Queue (FIFO) — neighbors are added to the back and visited from the front; ensures level-by-level traversal
- Shortest path — BFS finds the shortest path in terms of number of hops (edges), not edge weights
- Level / layer — all nodes at the same distance from the start
A colleague describes their algorithm as: "DFS with a visited set to detect cycles." What does this mean?
DFS tracks visited nodes; revisiting a node in the current path = cycle detected. DFS cycle detection vocabulary:
- Depth-First Search — explore as deep as possible along one path before backtracking; uses recursion or a stack
- Visited set — records nodes already explored; prevents infinite loops in cyclic graphs
- Cycle — a path that leads back to an already-visited node
- Back edge — a DFS edge that connects to an ancestor in the current path (indicates a cycle)
A tree traversal function is described as: "visits the left subtree, then the node, then the right subtree." Which traversal is this?
In-order traversal: left → node → right. Binary tree traversal vocabulary:
- Pre-order — node, left, right; useful for copying a tree or generating prefix expressions
- In-order — left, node, right; on a BST, produces nodes in sorted order
- Post-order — left, right, node; useful for deleting a tree (delete children before parent) or postfix expressions
- Level-order (BFS) — visits nodes level by level from root down
A design document says: "We use Dijkstra's algorithm to find the lowest-cost route." What is the key difference between Dijkstra's and BFS?
Dijkstra's handles weighted edges (cost); BFS treats all edges as equal (hops). Shortest path algorithm vocabulary:
- BFS — O(V+E); shortest path by number of edges; all edges treated as weight 1
- Dijkstra's — O((V+E) log V) with a priority queue; shortest path by total weight; requires non-negative edge weights
- Bellman-Ford — O(V×E); handles negative edge weights; slower
- A* — Dijkstra's with a heuristic; faster in practice when a good heuristic exists (e.g., geographic distance)
A PR adds a topological sort to the build system. What does topological sort mean in plain English?
Ordering DAG nodes so each node comes before nodes it depends on. Topological sort vocabulary:
- Directed Acyclic Graph (DAG) — directed graph with no cycles; prerequisite for topological sort
- Topological order — a linear ordering where for every edge (u → v), u appears before v
- Use cases: build systems (compile A before B), task scheduling, package dependency resolution, course prerequisites