Skip to content
Concept ยท Data Structures and Algorithms

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

By Younus FardeenUpdated 11 Nov 202610 min read
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 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

ApplicationVerticesEdgesAlgorithm used
Maps and navigationPlaces or junctionsRoads, weighted by distance or timeDijkstra's algorithm, BFS when unweighted
Social networksPeople or accountsFriendships or followsBFS, connected components
Dependency resolution and build systemsPackages, tasks, courses"Needs" relationshipsTopological sort
Recommendation systemsUsers and itemsPurchases, views, ratingsCounting shared neighbours, graph traversal
Web crawling and search rankingWeb pagesHyperlinksBFS, PageRank
Network routingRoutersLinks with a costDijkstra's algorithm (link-state routing)
Scheduling and timetablesJobs, exams or roomsConflicts between themGraph colouring, matching
CompilersBlocks of codePossible jumps between blocksControl-flow graph analysis
Fraud and ring detectionAccountsShared devices or transfersConnected components
Puzzles and game searchGame statesLegal movesBFS, 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.

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

AlgorithmSolvesTime
BFSFewest edges, nearest match, level orderO(V + E)
DFSConnectivity, cycles, components, backtrackingO(V + E)
Dijkstra's (binary heap)Shortest path with non-negative weightsO((V + E) log V)
Bellman-FordShortest path when weights can be negativeO(V * E)
Floyd-WarshallShortest paths between all pairsO(V^3)
Topological sort (Kahn's)Ordering a DAG, detecting a directed cycleO(V + E)
Union-Find (disjoint set)Merging groups, minimum spanning tree with Kruskal'sAlmost O(1) per operation

Practice problems, in order

  1. Find if Path Exists in Graph
  2. Number of Provinces (social groups)
  3. Course Schedule II (topological sort)
  4. Network Delay Time (Dijkstra's)
  5. Path with Maximum Probability
  6. Cheapest Flights Within K Stops
  7. Evaluate Division (weighted graph)
  8. 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

Learn this with mentors

Programmes for builders and engineers with admissions open: live classes, mentors and project work.

Continue learning

Concept

Graph data structure

Vertices, edges, BFS, DFS and cycle checks with tested code

Open →
Explainer

Applications of queue

Where queues are used: scheduling, BFS, buffers, with code.

Open →
Concept

Applications of stack

Call stack, undo, brackets, postfix, DFS and more, with runnable code

Open →