Graph Theory for Software Engineers: Practical Concepts
graph-theoryalgorithmsdata-structuresbfsdfsshortest-pathtopological-sortneo4j
Loading…
Back openDesk Edu for a sovereign, open-source education — every vote counts.
Vote nowGraphs aren't abstract math — they're everywhere in software:
Understanding the algorithms that operate on these structures will make you a better engineer whether you are building a recommendation engine, a dependency resolver, or an AI agent backed by a knowledge graph.
BFS explores the graph level by level. It visits all neighbours of a node before moving to neighbours-of-neighbours. This guarantees the shortest path in unweighted graphs — the first time you reach a target, you have found the path with fewest edges.
from collections import deque
def bfs_shortest_path(graph, start, target):
visited = {start}
queue = deque([(start, [start])])
while queue:
node, path = queue.popleft()
if node == target:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
When to use it: Finding degrees of separation in a social network, crawling a sitemap, discovering all reachable nodes in an infrastructure graph. Time complexity: O(V + E).
DFS explores as far as possible along each branch before backtracking. It uses a stack (implicitly via recursion, or explicitly with a manual stack) and is the foundation for cycle detection and topological ordering.
def has_cycle(graph):
visited = set()
rec_stack = set()
def dfs(node):
visited.add(node)
rec_stack.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
if dfs(neighbor):
return True
elif neighbor in rec_stack:
return True
rec_stack.discard(node)
return False
for node in graph:
if node not in visited:
if dfs(node):
return True
return False
When to use it: Detecting circular imports in Python modules, finding deadlock cycles in database transactions, solving maze-like puzzles. Time complexity: O(V + E).
BFS finds the shortest path when every edge has equal cost, but many real-world graphs have weighted edges. Dijkstra's algorithm finds the shortest path from a source to all other nodes in a graph with non-negative weights.
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_dist, node = heapq.heappop(pq)
if current_dist > distances[node]:
continue
for neighbor, weight in graph[node]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
When to use it: Computing the fastest route in a road network, finding the lowest-latency path through a microservice call graph, optimising data pipeline costs. Time complexity: O((V + E) log V) with a binary heap.
Dijkstra's algorithm is available natively in Neo4j through the Graph Data Science library:
MATCH (source:Location {name: 'Berlin'})
CALL gds.shortestPath.dijkstra.stream('road-network', {
sourceNode: source,
relationshipWeightProperty: 'distance_km'
})
YIELD nodeIds, totalCost
RETURN [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS route, totalCost
A topological ordering of a directed acyclic graph (DAG) is a linear sequence where every node appears before all nodes it depends on. This is the fundamental algorithm behind every build system and package manager.
Kahn's algorithm uses in-degree counting to produce a topological order:
from collections import deque, defaultdict
def topological_sort(dependencies):
# dependencies: dict of {module: [list of prerequisites]}
in_degree = {node: 0 for node in dependencies}
for node in dependencies:
for prereq in dependencies[node]:
in_degree[node] = in_degree.get(node, 0) + 1
queue = deque([n for n, d in in_degree.items() if d == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for dependent in dependencies.get(node, []):
in_degree[dependent] -= 1
if in_degree[dependent] == 0:
queue.append(dependent)
return result if len(result) == len(in_degree) else None # None = cycle detected
When to use it: Ordering build targets in a Makefile or Turborepo pipeline, resolving npm package installation order, scheduling batch data processing jobs.
A strongly connected component (SCC) is a maximal subgraph where every node can reach every other node. In dependency graphs, SCCs larger than one node represent circular dependencies — a class of bug that causes stack overflows in recursive resolvers and deadlocks in distributed transactions.
def tarjan_scc(graph):
index_counter = [0]
stack = []
lowlink = {}
index = {}
result = []
def strongconnect(node):
index[node] = index_counter[0]
lowlink[node] = index_counter[0]
index_counter[0] += 1
stack.append(node)
for neighbor in graph.get(node, []):
if neighbor not in index:
strongconnect(neighbor)
lowlink[node] = min(lowlink[node], lowlink[neighbor])
elif neighbor in stack:
lowlink[node] = min(lowlink[node], index[neighbor])
if lowlink[node] == index[node]:
scc = []
while True:
w = stack.pop()
scc.append(w)
if w == node:
break
result.append(scc)
for v in graph:
if v not in index:
strongconnect(v)
return result
When to use it: Detecting circular package dependencies, identifying deadlock cycles in resource allocation graphs, decomposing a service mesh into transactional boundaries.
Which nodes matter most? Centrality metrics quantify importance in a graph. The choice of metric depends entirely on what "importance" means in your domain.
import networkx as nx
G = nx.Graph()
G.add_edges_from([("A", "B"), ("B", "C"), ("A", "C"), ("C", "D")])
degree = nx.degree_centrality(G)
betweenness = nx.betweenness_centrality(G)
pagerank = nx.pagerank(G)
| Metric | What It Measures | Software Engineering Use Case |
|---|---|---|
| Degree centrality | Number of direct connections | Finding the most-connected microservice (highest blast radius) |
| Betweenness centrality | How often a node lies on shortest paths between others | Identifying critical API gateways — single points of failure |
| Closeness centrality | Average distance to all other nodes | Choosing the best node for a cache or data replication seed |
| PageRank | Importance propagated from important neighbours | Ranking entities in a knowledge graph by domain authority |
In the example graph above, node C has the highest betweenness centrality because every path between {A, B} and D passes through it — making it the single point of failure to monitor and replicate.
Choose based on your use case:
| Representation | Storage | Add Edge | Check Edge | Neighbors |
|---|---|---|---|---|
| Adjacency Matrix | O(V²) | O(1) | O(1) | O(V) |
| Adjacency List | O(V+E) | O(1) | O(deg(V)) | O(deg(V)) |
| Edge List | O(E) | O(1) | O(E) | O(E) |
For most applications, the adjacency list wins — it is compact and iterating neighbours is fast. Real-world graphs (social networks, knowledge graphs, service meshes) are sparse: millions of nodes but each connected to only a tiny fraction of the total. Adjacency matrices waste O(V²) space on zeros.
Every algorithm in this article translates directly to graph database queries. Neo4j exposes BFS, shortest-path, and centrality through Cypher and the Graph Data Science library.
Multi-hop relationship traversal (the Cypher equivalent of BFS):
MATCH (a:Person {name: "Alice"})-[:KNOWS*1..3]->(b:Person)
RETURN DISTINCT b.name AS reachable_friends
Shortest path between two entities:
MATCH p = shortestPath(
(a:Person {name: "Alice"})-[:KNOWS*]-(b:Person {name: "David"})
)
RETURN [n IN nodes(p) | n.name] AS path
PageRank on a knowledge graph:
CALL gds.pageRank.stream('entity-graph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS entity, score
ORDER BY score DESC
LIMIT 10
These patterns form the backbone of GraphRAG retrieval pipelines, where vector similarity identifies relevant chunks and graph traversal expands them to include connected entities, relationships, and metadata.
Every knowledge graph algorithm builds on these fundamentals:
Understanding these primitives gives you the vocabulary to design better retrieval pipelines, debug performance issues in graph-backed AI systems, and choose the right algorithm for the job. Graph theory is not classroom mathematics — it is the engineering practice of connected data.