Graph applications
Graphs model relationships and networks: anything that connects “things” with optional direction and cost. The table below maps domains to vertices and edges; later lessons show representations and algorithms in C.
On this page
- Real-world and systems uses (table)
- Why a graph fits—quick patterns
- Link to representation and types next
1) Domains and examples
| Area | Example | Graph role |
|---|---|---|
| Transport | Roads, transit, flight routes | Places = vertices; roads or flights = weighted edges (distance, time, fare). |
| Social / web | Followers, citations, hyperlinks | People or pages = vertices; follows or links = directed edges. |
| Scheduling | Task prerequisites, build systems | Tasks = vertices; dependency “A before B” = directed edge; often a DAG. |
| Compilers / workflows | Control flow, resource allocation | Basic blocks or states = vertices; jumps or transitions = edges. |
| Games / puzzles | Board states, word ladders | States = vertices; legal moves = edges; BFS finds shortest move count (unweighted). |
| Electrical / utility | Power grids, pipelines | Stations = vertices; lines = edges; capacities or resistances as weights. |
| Clustering | Similarity networks | Items = vertices; similarity threshold creates edges for community detection. |
2) Why not just a tree?
When relationships are many-to-many, bidirectional, or include cycles, a tree is too rigid. Graphs expose alternative routes, feedback loops, and global connectivity—exactly what shortest-path, MST, and SCC algorithms exploit.
Key takeaway
If your problem has networks, maps, dependencies, or states with multiple transitions, model it as a graph—then choose type (directed, weighted, …) and representation (matrix vs list) before coding BFS/DFS and beyond.
Next up: Graph representation · Graph versus tree · Graph types