---
title: Applications of Graph in Data Structure, With Code Examples
url: https://www.masaischool.com/resources/applications-of-graph-in-data-structure
description: Applications of graphs in data structures: maps, social networks, build order, recommendations, web crawling and routing, each with a tiny runnable example.
updated: 2026-11-17
publisher: Masai (https://www.masaischool.com)
---

# Applications of Graph in Data Structure: Real-World Uses and Code Examples

> **Short answer**
>
> 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](https://www.masaischool.com/resources/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 ] ] 3

Asha 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](https://www.masaischool.com/resources/graph-data-structure-explained).

### 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 detected

The 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](https://www.masaischool.com/resources/dynamic-programming-explained) 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](https://research.google/pubs/the-anatomy-of-a-large-scale-hypertextual-web-search-engine/). A real crawler must also follow [robots.txt rules](https://www.rfc-editor.org/rfc/rfc9309.html) 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](https://www.rfc-editor.org/rfc/rfc2328.html), 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

1. [Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/)
2. [Number of Provinces](https://leetcode.com/problems/number-of-provinces/) (social groups)
3. [Course Schedule II](https://leetcode.com/problems/course-schedule-ii/) (topological sort)
4. [Network Delay Time](https://leetcode.com/problems/network-delay-time/) (Dijkstra's)
5. [Path with Maximum Probability](https://leetcode.com/problems/path-with-maximum-probability/)
6. [Cheapest Flights Within K Stops](https://leetcode.com/problems/cheapest-flights-within-k-stops/)
7. [Evaluate Division](https://leetcode.com/problems/evaluate-division/) (weighted graph)
8. [Word Ladder](https://leetcode.com/problems/word-ladder/) (BFS over states)

Masai's longer guide: [Introduction to Data structures - Graphs and its Applications](https://www.masaischool.com/blog/applications-of-graph-data-structure/). Similar structure-by-use pages: [applications of queue](https://www.masaischool.com/resources/applications-of-queue-in-data-structure), [applications of stack](https://www.masaischool.com/resources/applications-of-stack-in-data-structure) and [applications of array](https://www.masaischool.com/resources/applications-of-array-in-data-structure). To build something with these ideas, browse the [software development projects](https://www.masaischool.com/resources/projects/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](https://www.rfc-editor.org/rfc/rfc2328.html)
- [Brin and Page 1998: the web's link graph as an input to PageRank](https://research.google/pubs/the-anatomy-of-a-large-scale-hypertextual-web-search-engine/)
- [graphlib.TopologicalSorter, added in Python 3.9, raises CycleError](https://docs.python.org/3/library/graphlib.html)
- [Dijkstra's complexity with a binary heap](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
- [Robots Exclusion Protocol for crawlers](https://www.rfc-editor.org/rfc/rfc9309.html)
- [Existing Masai post (HTTP 200 on 11 Nov 2026)](https://www.masaischool.com/blog/applications-of-graph-data-structure/)
