Rung 5: Graph Algorithm Showcase

Month: M6–M7 (December 2026 – January 2027) Platform: GitHub (primary) + optional blog post linking to repo Hard Gate: No — but this rung earns its place by being the most visible technical work in the portfolio. It bridges theory and application in a way nothing else in the ladder does.

What It Is

A GitHub repository named graph-algorithm-showcase containing 5 complete graph algorithm implementations, each demonstrated on a real or realistic dataset with visible output. Not toy examples with 5 nodes. Not LeetCode-style input/output. Actual computations on actual data that produce results a non-programmer could look at and understand.

The goal is to make the algorithms do something interesting, not just run correctly. This is the rung where you stop proving you understand algorithms and start proving you can apply them.

The 5 Algorithms and Their Demonstrations

1. BFS on a Maze — Shortest Path Visualization

What you build: A maze solver using BFS that finds the shortest path from start to finish, displayed as ASCII output in the terminal.

Input format: A 2D grid loaded from a .txt file where # = wall, . = open cell, S = start, E = end.

Output: The original maze printed with the shortest path marked in *, plus the path length.

Example output:

#####S####
#....#...#
#.###.#.##
#.#...#..E
##########
Path found: 12 steps
S → (0,5) → (1,5) → ... → E

Why BFS and not DFS: The blog/README must explain why BFS guarantees shortest path and DFS does not. Level-by-level expansion, the invariant, the proof sketch.

Edge cases to handle: No path exists, maze with multiple routes (BFS finds shortest), very large maze (benchmark your implementation on a 100x100 grid).

Dataset source: Generate programmatically with a random maze generator (DFS-based maze generation is a good exercise here), or use one of the public maze datasets online.

2. Dijkstra on a City Road Network

What you build: Dijkstra’s shortest path implementation on a weighted graph representing a road network, finding the minimum-distance route between two locations.

Input format: Either (a) real OpenStreetMap data for a small area exported as a JSON/CSV edge list, or (b) a hand-crafted fictional city with at least 20 nodes and 40 edges with realistic distances in km.

Output: The shortest path between two user-specified nodes (city names or IDs), total distance, and the sequence of nodes visited.

Example output:

Shortest path from "Central Station" to "Airport":
Central Station → MG Road → Outer Ring Road → Airport
Total distance: 23.7 km

What the README must explain: Why Dijkstra fails on negative-weight edges. What the priority queue is doing and why a naive implementation (relaxing all edges repeatedly) is O(VE) vs O((V+E) log V) with a min-heap.

Real data option: Export a small city graph from OpenStreetMap using the osmnx Python library or any online OSM export tool. Even a 50-node subgraph of your city in Chennai/India is more compelling than a made-up one.

Fictional data option: Create fictional_city.json with nodes (city areas) and edges (roads with distances). Document why you chose the graph structure.

3. Union-Find: Connected Components in a Social Network

What you build: A Union-Find (Disjoint Set Union) implementation used to find all connected components in a social network graph — i.e., groups of people who are mutually connected (directly or indirectly).

Input format: A CSV with columns person_a, person_b representing friendship links. Use either a real small dataset (Stanford SNAP has public social network datasets) or a synthetic one you generate.

Output:

Total people: 150
Connected components found: 8

Component 1 (47 people): Alice, Bob, Charlie, ... [top 5 shown]
Component 2 (31 people): Dave, Eve, Frank, ...
...
Component 8 (2 people): Isolated pair

What the README must explain: Path compression and union by rank — not just “these optimizations exist” but why they bring the amortized cost to near O(1) per operation. The inverse Ackermann function gets mentioned here; you don’t need to prove it, but you need to explain what “amortized near-constant” actually means.

Dataset option: Stanford SNAP ego-Facebook dataset (public, free). Use the first 200 nodes for tractability.

4. Topological Sort on a Dependency Graph

What you build: A topological sort implementation (Kahn’s algorithm OR DFS-based, your choice — implement both if you want to show the contrast) applied to a dependency resolution problem.

The scenario: You have a fictional build system where tasks depend on other tasks (like Makefile targets or npm packages). Given the dependency graph, output a valid build order. Also detect and report cycles (which make topological sort impossible).

Input format: A JSON file defining tasks and their dependencies:

{
  "compile_utils": [],
  "compile_core": ["compile_utils"],
  "run_tests": ["compile_core", "compile_utils"],
  "package": ["run_tests"],
  "deploy": ["package"]
}

Output:

Valid build order found:
1. compile_utils
2. compile_core
3. run_tests
4. package
5. deploy

All dependencies satisfied.

Cycle detection output:

ERROR: Cycle detected!
Cycle: A → B → C → A
Build order cannot be determined.

What the README must explain: The difference between Kahn’s (BFS-based, in-degree tracking) and DFS-based topological sort. When each is more natural. Why topological sort only works on DAGs (Directed Acyclic Graphs).

Extra credit: Use real npm package dependency data — pick any small popular package and export its full dependency tree using npm ls --json.

5. Minimum Spanning Tree: Minimum Cost to Connect Cities

What you build: Kruskal’s algorithm (or Prim’s — implement both for full marks) to find the minimum spanning tree of a weighted graph, presented as “the minimum cable length needed to connect N cities with fiber optic lines.”

Input format: A JSON or CSV with cities (nodes) and possible cable routes (edges) with costs in km or dollars.

Output:

Minimum Spanning Tree found!
Selected connections (12 total):
Chennai → Bangalore: 347 km
Bangalore → Hyderabad: 574 km
...

Total minimum cable length: 4,283 km
Cost if excluded: 7,891 km (savings: 3,608 km)

What the README must explain: The cut property of MSTs (why greedily picking the minimum weight edge that doesn’t form a cycle gives a globally optimal result). The difference between Kruskal’s (edge-sorted, uses Union-Find) and Prim’s (vertex-greedy, uses priority queue). Time complexity of both.

Dataset: Use major Indian cities as nodes (Chennai, Bangalore, Hyderabad, Mumbai, Delhi, Kolkata, Pune, Ahmedabad) with approximate road distances as edge weights. This makes the output feel real.

Repository Structure

graph-algorithm-showcase/
├── README.md                    # Overview, what each demo does, how to run
├── 01_bfs_maze/
│   ├── maze_solver.java         # (or .cpp or .py)
│   ├── mazes/
│   │   ├── easy.txt
│   │   ├── medium.txt
│   │   └── no_path.txt
│   └── README.md
├── 02_dijkstra_roads/
│   ├── dijkstra.java
│   ├── data/
│   │   └── city_graph.json
│   └── README.md
├── 03_union_find_social/
│   ├── union_find.java
│   ├── data/
│   │   └── friendships.csv
│   └── README.md
├── 04_topological_sort_deps/
│   ├── topo_sort.java
│   ├── data/
│   │   ├── build_tasks.json
│   │   └── cyclic_example.json
│   └── README.md
└── 05_mst_cities/
    ├── kruskal.java
    ├── data/
    │   └── india_cities.json
    └── README.md

Acceptance Criteria

  • All 5 algorithms implemented and runnable with the provided data files

  • Each subdirectory has its own README explaining the algorithm, the dataset, and the output

  • The root README has a one-paragraph summary of what each demo computes and links to each subdirectory

  • Someone unfamiliar with graphs can read the output of each demo and understand what was computed (test this with a non-technical friend or colleague)

  • At least one algorithm is benchmarked — run it on a larger synthetic dataset and report timing in the README (e.g., “Dijkstra on 1000-node graph: 4ms”)

  • Cycle detection is implemented in the topological sort demo and tested with a cyclic graph

Signal It Sends

Most DSA practice is invisible — it happens on LeetCode and disappears into a solved count. This repository is legible. Someone can clone it, run it, and see algorithms solving recognizable problems. That transition from “solves contrived puzzles” to “applies algorithms to real structures” is exactly what separates a practitioner from someone who studied for interviews.

The graph showcase also demonstrates something subtle: you had to choose your datasets. That choice requires understanding what makes a graph problem interesting, which requires deeper comprehension than just implementing the algorithm correctly.

Platform Notes

  • GitHub: primary home, make the root README excellent — it’s what people see when they land on the repo

  • Optional: a single blog post titled “5 Graph Algorithms, 5 Real Datasets” that links to the repo and walks through the most interesting demo (BFS maze or Dijkstra on real road data tend to get the most engagement)

  • Pin this repo to your GitHub profile

Month M6–M7 Timeline

Week

Goal

M6 Week 1

Repo setup, BFS maze solver complete and tested

M6 Week 2

Dijkstra on city graph complete

M7 Week 1

Union-Find social network + topological sort complete

M7 Week 2

MST cities + root README + any benchmarking

Navigation: ← Rung 4: LeetCode 100 | Portfolio README | Rung 6: DP Handbook →