# Graph Algorithms and Traversal

Computer Science I · Algorithmics · https://tryals.app/learn/computer-science-i/graph-algorithms-and-traversal

## Network Traversal: BFS vs DFS

Once data is a graph, **traversal** (systematically visiting vertices along edges) is the fundamental operation. Two strategies dominate, differing only in the data structure and order of exploration.

| Strategy | Data Structure | Exploration Pattern | Key Use Case |
| --- | --- | --- | --- |
| **BFS** | **Queue** (FIFO) | Ripples outward, level by level | **Shortest path** on unweighted graphs |
| **DFS** | **Stack** (LIFO) | Plunges deep, then backtracks | **Topological sorting** & cycle detection |

Both strategies visit each vertex and edge a constant number of times, running in **$O(V + E)$** time.

## Weighted Graphs & Pitfalls

For **weighted graphs** where edges carry costs, standard BFS fails. **Dijkstra's algorithm** greedily expands the nearest unsettled vertex using a **priority queue (heap)**, finding shortest paths when weights are non-negative.

$$\text{Complexity} = O(V + E)$$

> **Common pitfall:** Forgetting the **visited set**. In a cyclic graph, omitting this causes infinite loops or exponential re-exploration.

Every graph traversal must track visited vertices to guarantee termination and process each vertex exactly once.

## Practice questions

5 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. Order the steps of breadth-first search from a start vertex.

**Answer:**

1. Put the start vertex in the queue and mark it visited
2. Remove the front vertex from the queue
3. Visit each unvisited neighbour, marking it and adding it to the queue
4. Repeat until the queue is empty

**Why:** BFS seeds the queue, then repeatedly dequeues a vertex and enqueues its unvisited neighbours, rippling outward level by level. The FIFO queue is what produces the level-order and the shortest paths.

Page: https://tryals.app/practice/computer-science-i/graph-algorithms-and-traversal/order-the-steps-of-breadth-first-search-from-a-start-vertex

### 2. Swapping the queue in breadth-first search for a stack turns it into depth-first search, changing what the algorithm finds.

**Answer:** True

**Why:** True. FIFO expands nodes in order of distance from the start, so the first time BFS reaches a node it has found the *shortest* path; LIFO plunges down one branch first, so DFS finds *a* path. One line changes the guarantee, which is why the container choice is the algorithm.

Page: https://tryals.app/practice/computer-science-i/graph-algorithms-and-traversal/swapping-the-queue-in-breadth-first-search-for-a-stack-turns-it-into

### 3. A graph traversal on a graph with cycles runs forever without a visited set. Why does the set fix it, and what does it cost?

A. Because a cycle returns you to a node you already expanded
B. It costs nothing, since the set replaces the frontier structure
C. Because cycles are detected and removed by the set
D. Because the set orders the nodes, preventing revisits

**Answer:** A. Because a cycle returns you to a node you already expanded

**Why:** Without marking, a cycle is an infinite loop; with it, every node is expanded once and the traversal is O(V+E). The memory is O(V) and unavoidable, which becomes the binding constraint on enormous graphs, where bloom filters and external-memory algorithms replace the exact set.

Page: https://tryals.app/practice/computer-science-i/graph-algorithms-and-traversal/a-graph-traversal-on-a-graph-with-cycles-runs-forever-without-a

### 4. Select every true statement about graph traversal.

A. A traversal without a visited set can loop forever on a cyclic graph
B. BFS finds the fewest-edge path from the start in an unweighted graph
C. Dijkstra's algorithm needs a priority queue
D. DFS uses a queue
E. BFS and DFS both run in O(V + E)

**Answer:** A. A traversal without a visited set can loop forever on a cyclic graph; B. BFS finds the fewest-edge path from the start in an unweighted graph; C. Dijkstra's algorithm needs a priority queue; E. BFS and DFS both run in O(V + E)

**Why:** Both traversals are O(V + E); BFS gives shortest unweighted paths; Dijkstra uses a priority queue; and the visited set prevents infinite loops. 'DFS uses a queue' is false. DFS uses a stack.

Page: https://tryals.app/practice/computer-science-i/graph-algorithms-and-traversal/select-every-true-statement-about-graph-traversal

### 5. Sort each task by which traversal is the natural fit.

**Answer:**

- Use BFS: Find the shortest route in an unweighted maze, Find the nearest reachable vertex by edge count
- Use DFS: Detect a cycle in a dependency graph, Topologically sort tasks with dependencies

**Why:** BFS suits shortest-edge and nearest-first questions; DFS suits cycle detection and topological sorting. Matching the traversal's exploration order to the task is the whole skill.

Page: https://tryals.app/practice/computer-science-i/graph-algorithms-and-traversal/sort-each-task-by-which-traversal-is-the-natural-fit