Graph Algorithms — Core Concepts

Why graph algorithms matter

Graphs model relationships. Social networks, road maps, dependency trees, web crawlers, recommendation engines — all of these are graph problems. Understanding a handful of core graph algorithms unlocks solutions to a huge range of practical problems.

Representing graphs in Python

The two most common representations:

Adjacency list (most common in Python):

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C"],
    "E": ["C"]
}

Adjacency matrix (useful for dense graphs or when you need O(1) edge lookup):

#     A  B  C  D  E
# A [[0, 1, 1, 0, 0],
# B  [1, 0, 0, 1, 0],
# C  [1, 0, 0, 1, 1],
# D  [0, 1, 1, 0, 0],
# E  [0, 0, 1, 0, 0]]

Adjacency lists use less memory for sparse graphs (most real-world graphs) and are more natural in Python.

Breadth-first search (BFS)

BFS explores nodes level by level, starting from a source. It uses a queue (first-in, first-out):

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

When to use BFS: finding the shortest path in an unweighted graph, level-order traversal, checking if two nodes are connected.

Depth-first search (DFS)

DFS explores as deep as possible before backtracking. It uses a stack (or recursion):

def dfs(graph, start):
    visited = set()
    stack = [start]
    order = []
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            order.append(node)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    return order

When to use DFS: detecting cycles, topological sorting, finding connected components, solving mazes.

Shortest path with Dijkstra’s algorithm

When edges have different weights (costs), BFS is not enough. Dijkstra’s algorithm finds the shortest weighted path:

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_dist, current = heapq.heappop(priority_queue)
        if current_dist > distances[current]:
            continue
        for neighbor, weight in graph[current]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances

Here, the graph maps each node to a list of (neighbor, weight) tuples.

Cycle detection

Cycles can cause infinite loops in graph traversal. Detecting them is crucial:

• Undirected graphs: if DFS encounters a visited node that is not the parent, there is a cycle.
• Directed graphs: use DFS with three states (unvisited, in-progress, completed). If you visit an in-progress node, there is a cycle.

Topological sort

For directed acyclic graphs (DAGs) — like task dependencies — topological sort produces an ordering where every node comes before its dependents:

from collections import deque

def topological_sort(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    queue = deque([n for n in in_degree if in_degree[n] == 0])
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(order) != len(graph):
        raise ValueError("Graph has a cycle")
    return order

Common misconception

“Graphs are only for academic problems.” In reality, every time you use a package manager (pip resolves dependency graphs), a GPS (shortest path on a road graph), or scroll a social media feed (recommendation graph), graph algorithms are running behind the scenes.

One thing to remember: BFS finds shortest paths in unweighted graphs, DFS explores structure and detects cycles, and Dijkstra handles weighted shortest paths. These three cover the vast majority of practical graph problems.