A graph models things and the links between them, so it is used wherever relationships matter. Main applications: shortest routes in maps, social networks, dependency and build order, recommendations, web crawling and page ranking, and network routing. They rely on breadth-first search (BFS), depth-first search (DFS), Dijkstra's algorithm or topological sort.
A graph is the right tool when the data is about relationships: which place connects to which, who knows whom, what depends on what. If you need a refresher on vertices, edges and BFS, read graph data structure explained first.
Each application below has a small example that runs as written, on made-up data. They were run on Python 3.9 and Node 24 on 11 November 2026 and the output shown is the real output.
Main applications of a graph
| Application | Vertices | Edges | Algorithm used |
|---|---|---|---|
| Maps and navigation | Places or junctions | Roads, weighted by distance or time | Dijkstra's algorithm, BFS when unweighted |
| Social networks | People or accounts | Friendships or follows | BFS, connected components |
| Dependency resolution and build systems | Packages, tasks, courses | "Needs" relationships | Topological sort |
| Recommendation systems | Users and items | Purchases, views, ratings | Counting shared neighbours, graph traversal |
| Web crawling and search ranking | Web pages | Hyperlinks | BFS, PageRank |
| Network routing | Routers | Links with a cost | Dijkstra's algorithm (link-state routing) |
| Scheduling and timetables | Jobs, exams or rooms | Conflicts between them | Graph colouring, matching |
| Compilers | Blocks of code | Possible jumps between blocks | Control-flow graph analysis |
| Fraud and ring detection | Accounts | Shared devices or transfers | Connected components |
| Puzzles and game search | Game states | Legal moves | BFS, DFS |
Six applications, each with a runnable example
Application 1: shortest path in maps
A road map is a weighted graph. To find the shortest route, use Dijkstra's algorithm: always extend the closest unfinished place first, using a priority queue (a heap). The edge weights must not be negative. With a binary heap it takes O((V + E) log V). Navigation apps add heavy optimisation on top, but this is the core idea.
import heapq
roads = { # distances in km
"Home": {"Metro": 2, "Mall": 5},
"Metro": {"Home": 2, "Mall": 2, "Office": 7},
"Mall": {"Home": 5, "Metro": 2, "Office": 3},
"Office": {"Metro": 7, "Mall": 3},
}
def shortest_route(graph, start, goal):
best = {start: 0}
came_from = {}
heap = [(0, start)] # (distance so far, node)
while heap:
dist, node = heapq.heappop(heap)
if node == goal:
break
if dist > best[node]:
continue # a shorter way to this node was already found
for nxt, km in graph[node].items():
new_dist = dist + km
if new_dist < best.get(nxt, float("inf")):
best[nxt] = new_dist
came_from[nxt] = node
heapq.heappush(heap, (new_dist, nxt))
path = [goal]
while path[-1] != start:
path.append(came_from[path[-1]])
return best[goal], path[::-1]
print(shortest_route(roads, "Home", "Office"))Output: (7, ['Home', 'Metro', 'Mall', 'Office'])
Home, Mall, Office costs 8 km and Home, Metro, Office costs 9 km, but Home, Metro, Mall, Office costs only 2 + 2 + 3 = 7 km. If every road counted the same, plain BFS would be enough.
Application 2: social networks
On a social network people are vertices and friendships are edges. "People you may know" looks for friends of friends and ranks them by how many mutual friends they share. "Degrees of separation" is the BFS distance between two people.
const friends = {
asha: ["ben", "chen"],
ben: ["asha", "dev"],
chen: ["asha", "dev", "esha"],
dev: ["ben", "chen", "fay"],
esha: ["chen"],
fay: ["dev"],
};
// "People you may know": friends of friends, ranked by number of mutual friends
function suggestions(user) {
const mutual = new Map();
for (const f of friends[user]) {
for (const fof of friends[f]) {
if (fof !== user && !friends[user].includes(fof)) {
mutual.set(fof, (mutual.get(fof) || 0) + 1);
}
}
}
return [...mutual].sort((a, b) => b[1] - a[1]);
}
// "Degrees of separation": the BFS distance between two people
function degrees(a, b) {
const dist = { [a]: 0 };
const queue = [a];
for (let i = 0; i < queue.length; i++) {
for (const next of friends[queue[i]]) {
if (!(next in dist)) {
dist[next] = dist[queue[i]] + 1;
queue.push(next);
}
}
}
return dist[b];
}
console.log(suggestions("asha"));
console.log(degrees("asha", "fay"));Output:
[ [ 'dev', 2 ], [ 'esha', 1 ] ]
3Asha and Dev share two friends, Ben and Chen, so Dev ranks first. Asha is three steps from Fay: Asha, Ben, Dev, Fay. Finding groups of connected people, or an isolated group, uses connected components, covered in the graph basics page.
Application 3: dependency resolution and topological sort
When task B needs task A, draw an edge from A to B. The result must be a DAG (directed acyclic graph) or the tasks can never all be done. A topological sort lists the tasks so that every task comes after the ones it needs. Build tools, package installers and course planners all depend on this idea. Kahn's algorithm below repeatedly takes every task that has nothing left to wait for, and a leftover task means a circular dependency.
from collections import deque
from graphlib import CycleError, TopologicalSorter
# needs[x] = what must be built before x
needs = {
"app": ["api", "ui"],
"api": ["db", "utils"],
"ui": ["utils"],
"db": [],
"utils": [],
}
def build_order(needs):
waiting = {name: len(deps) for name, deps in needs.items()}
used_by = {name: [] for name in needs}
for name, deps in needs.items():
for dep in deps:
used_by[dep].append(name)
ready = deque(sorted(n for n, k in waiting.items() if k == 0))
order = []
while ready:
name = ready.popleft()
order.append(name)
for user in used_by[name]:
waiting[user] -= 1
if waiting[user] == 0:
ready.append(user)
if len(order) < len(needs):
raise ValueError("circular dependency")
return order
print(build_order(needs))
# The standard library (Python 3.9+) already has this:
print(len(list(TopologicalSorter(needs).static_order())), "packages ordered")
try:
list(TopologicalSorter({"a": ["b"], "b": ["a"]}).static_order())
except CycleError:
print("cycle detected")Output:
['db', 'utils', 'api', 'ui', 'app']
5 packages ordered
cycle detectedThe standard library has had graphlib.TopologicalSorter since Python 3.9, so you rarely write this by hand outside interviews. More than one valid order can exist; any order that respects every "needs" edge is correct. See dynamic programming for another place where processing in dependency order matters.
Application 4: recommendation systems
Store users and items as two kinds of vertices, with an edge for every purchase. Two users who bought the same item are two steps apart. To recommend items to one user, find the people connected to them through shared items, then count which other items those people bought.
bought = {
"asha": {"python book", "laptop stand", "mouse"},
"ben": {"python book", "mouse", "headphones"},
"chen": {"laptop stand", "keyboard"},
"dev": {"python book", "headphones"},
}
def recommend(user):
mine = bought[user]
scores = {}
for other, items in bought.items():
if other == user:
continue
overlap = len(mine & items) # shared items link two users
if overlap:
for item in items - mine: # items this user does not have yet
scores[item] = scores.get(item, 0) + overlap
return sorted(scores.items(), key=lambda kv: (-kv[1], kv[0]))
print(recommend("asha"))Output: [('headphones', 3), ('keyboard', 1)]
Headphones score 3: Ben shares two of Asha's items and Dev shares one, and both bought headphones. Real systems add ratings, recency and machine learning, but "people connected to people like you" is a graph question at the core.
Application 5: web crawling and search ranking
The web is a directed graph: pages are vertices and links are edges. A crawler starts from a few pages, follows links in BFS order and keeps a visited set so that pages that link to each other do not trap it in a loop. Google's founders described the web's link graph as the input to their PageRank ranking in a 1998 paper. A real crawler must also follow robots.txt rules and limit its request rate.
from collections import deque
web = { # page -> links found on it (a pretend site)
"/": ["/courses", "/blog"],
"/courses": ["/", "/courses/python"],
"/blog": ["/", "/blog/graphs", "/courses/python"],
"/courses/python": ["/courses"],
"/blog/graphs": ["/blog", "/blog/trees"],
"/blog/trees": ["/blog/graphs"],
}
def crawl(start, max_depth):
seen = {start} # without this the crawler loops forever
queue = deque([(start, 0)])
order = []
while queue:
page, depth = queue.popleft()
order.append(page)
if depth == max_depth:
continue # visited, but do not follow its links
for link in web.get(page, []):
if link not in seen:
seen.add(link)
queue.append((link, depth + 1))
return order
print(crawl("/", 2))Output: ['/', '/courses', '/blog', '/courses/python', '/blog/graphs']
The crawl stops at depth 2, so /blog/trees, which is three clicks from the home page, is never visited. The pretend site lives in a dictionary, so the example makes no network requests.
Application 6: network routing
Routers and the links between them form a weighted graph. In link-state routing, such as OSPF (Open Shortest Path First), each router learns the whole map of routers and links. RFC 2328, the OSPF specification, describes that link-state database as a directed graph and builds a shortest-path tree, rooted at the router itself, with Dijkstra's algorithm. The routing table then only needs the first router to send each packet to.
import heapq
links = { # link cost, for example delay in ms
"R1": {"R2": 10, "R3": 30},
"R2": {"R1": 10, "R3": 5, "R4": 20},
"R3": {"R1": 30, "R2": 5, "R4": 10},
"R4": {"R2": 20, "R3": 10},
}
def routing_table(source):
"""For each destination: (total cost, first router to send the packet to)."""
cost = {source: 0}
first_hop = {}
done = set()
heap = [(0, source, None)]
while heap:
c, node, hop = heapq.heappop(heap)
if node in done:
continue
done.add(node)
if hop:
first_hop[node] = hop
for nxt, w in links[node].items():
if nxt not in done and c + w < cost.get(nxt, float("inf")):
cost[nxt] = c + w
heapq.heappush(heap, (c + w, nxt, hop or nxt))
return {dst: (cost[dst], first_hop[dst]) for dst in sorted(first_hop)}
print(routing_table("R1"))Output: {'R2': (10, 'R2'), 'R3': (15, 'R2'), 'R4': (25, 'R2')}
R1 reaches R3 by way of R2 at cost 15, because that beats the direct link of cost 30. Every route from R1 starts with the hop to R2.
Which algorithm for which application
| Algorithm | Solves | Time |
|---|---|---|
| BFS | Fewest edges, nearest match, level order | O(V + E) |
| DFS | Connectivity, cycles, components, backtracking | O(V + E) |
| Dijkstra's (binary heap) | Shortest path with non-negative weights | O((V + E) log V) |
| Bellman-Ford | Shortest path when weights can be negative | O(V * E) |
| Floyd-Warshall | Shortest paths between all pairs | O(V^3) |
| Topological sort (Kahn's) | Ordering a DAG, detecting a directed cycle | O(V + E) |
| Union-Find (disjoint set) | Merging groups, minimum spanning tree with Kruskal's | Almost O(1) per operation |
Practice problems, in order
- Find if Path Exists in Graph
- Number of Provinces (social groups)
- Course Schedule II (topological sort)
- Network Delay Time (Dijkstra's)
- Path with Maximum Probability
- Cheapest Flights Within K Stops
- Evaluate Division (weighted graph)
- Word Ladder (BFS over states)
Masai's longer guide: Introduction to Data structures - Graphs and its Applications. Similar structure-by-use pages: applications of queue, applications of stack and applications of array. To build something with these ideas, browse the software development projects list.
Frequently asked questions
What are the applications of graph in data structure?
Shortest routes in maps, social networks and friend suggestions, dependency and build ordering, recommendation systems, web crawling and page ranking, network routing, scheduling, compilers, fraud detection and puzzle or game search.
What are real-life examples of a graph?
A road map (places joined by roads), a social network (people joined by friendships), the web (pages joined by links), a computer network (routers joined by cables) and a course plan (courses joined by prerequisites) are all graphs.
Which algorithm is used to find the shortest path in a map?
Dijkstra's algorithm for roads with different lengths, and BFS when every edge counts the same. Navigation apps add many optimisations, but these are the textbook foundations.
Why is topological sort used for dependencies?
It lists the nodes of a directed acyclic graph so that every node appears after the nodes it depends on. A build tool or package installer can then process items in a safe order, and the same algorithm reports a circular dependency.
Where are directed and undirected graphs used?
Directed graphs suit one-way relationships such as follows, links and prerequisites. Undirected graphs suit mutual relationships such as friendships and two-way roads.
How is a graph different from a tree in applications?
A tree models strict hierarchies such as folders and organisation charts. A graph is used when items can connect in any pattern, have cycles or have several paths between them, as in maps and social networks.
Sources checked
- OSPF link-state database is a directed graph; shortest-path tree built with Dijkstra's algorithm
- Brin and Page 1998: the web's link graph as an input to PageRank
- graphlib.TopologicalSorter, added in Python 3.9, raises CycleError
- Dijkstra's complexity with a binary heap
- Robots Exclusion Protocol for crawlers
- Existing Masai post (HTTP 200 on 11 Nov 2026)
Learn this with mentors
Programmes for builders and engineers with admissions open: live classes, mentors and project work.


