Graph Algorithms Guide: Traversals, Shortest Paths, and More

Graphs are one of the most versatile data structures in computer science. A graph consists of vertices (nodes) and edges (connections) that can represent everything from social networks and web pages to road maps and dependency relationships. Mastering graph algorithms is essential for solving complex problems in networking, routing, recommendation systems, and more.

Graph Representations

Before applying algorithms, you need to understand how graphs are stored.

Adjacency Matrix

A 2D array where matrix[i][j] indicates an edge from vertex i to vertex j. Checking edge existence is O(1), but memory is O(V²) — impractical for large sparse graphs.

graph = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]

Adjacency List

Each vertex stores a list of neighbors. Memory is O(V + E), making it the default choice for most applications.

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
---

Edge List

A simple list of tuples (u, v, w) for each edge. Compact and easy to iterate, used in algorithms like Bellman-Ford and Kruskal where edge iteration is the primary operation.

Incidence Matrix

A V × E matrix where matrix[i][j] = 1 if vertex i is incident to edge j. While rarely used in practice due to its size, incidence matrices are useful in graph theory proofs and in network flow algorithms where edge-vertex relationships matter.

Graph Traversals

Breadth-First Search (BFS)

BFS explores a graph level by level. It uses a queue and guarantees the shortest path in unweighted graphs.

from collections import deque

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

Applications: Shortest path in unweighted graphs, web crawling, social network friend suggestions, garbage collection. BFS is also used in bipartite graph detection — if BFS encounters an edge connecting two vertices at the same level, the graph is not bipartite.

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack (or recursion).

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

Applications: Topological sorting, cycle detection, solving mazes, finding connected components, Sudoku solvers. DFS also enables articulation point (cut vertex) and bridge detection through discovery time tracking, which is critical in network reliability analysis.

Shortest Path Algorithms

Dijkstra’s Algorithm

Finds the shortest path from a source to all other vertices in a weighted graph with non-negative edges.

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

Complexity: O((V + E) log V) with a binary heap. Dijkstra is used in GPS navigation, network routing protocols (OSPF), and social network recommendation engines. Using a Fibonacci heap improves the theoretical complexity to O(V log V + E), but the constant factors make it rarely worthwhile in practice.

Bellman-Ford Algorithm

Handles negative edge weights and detects negative cycles. Slower than Dijkstra at O(V × E), but more flexible.

def bellman_ford(edges, V, start):
    distances = [float('inf')] * V
    distances[start] = 0

    for _ in range(V - 1):
        for u, v, w in edges:
            if distances[u] != float('inf') and distances[u] + w < distances[v]:
                distances[v] = distances[u] + w

    # Detect negative cycles
    for u, v, w in edges:
        if distances[u] != float('inf') and distances[u] + w < distances[v]:
            return None  # Negative cycle detected
    return distances

A* Search

A* extends Dijkstra with a heuristic function that estimates the distance from each node to the goal. The heuristic must be admissible (never overestimate) for optimality. A* is used extensively in game pathfinding, robotics navigation, and puzzle solving. The choice of heuristic dramatically affects performance — Manhattan distance for grid maps, Euclidean distance for continuous spaces.

Bidirectional Search

Bidirectional search runs two simultaneous searches — one forward from the source and one backward from the target. When the frontiers meet, the shortest path is found. This technique reduces the search space from O(b^d) to O(b^(d/2) + b^(d/2)) where b is the branching factor and d is the shortest path length. Bidirectional Dijkstra is commonly used in GPS routing engines and can be orders of magnitude faster than standard Dijkstra for point-to-point queries.

Minimum Spanning Trees

A spanning tree connects all vertices with the minimum total edge weight.

Kruskal’s Algorithm

Sorts edges by weight and adds them if they don’t create a cycle.

def kruskal(edges, V):
    edges.sort(key=lambda x: x[2])
    parent = list(range(V))
    mst = []

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        parent[find(x)] = find(y)

    for u, v, w in edges:
        if find(u) != find(v):
            union(u, v)
            mst.append((u, v, w))
    return mst

Complexity: O(E log E) due to sorting. Used in network design, clustering algorithms, and approximation algorithms.

Prim’s Algorithm

Grows the MST one vertex at a time, similar to Dijkstra. Prim’s uses a priority queue to select the minimum-weight edge connecting the current tree to an unvisited vertex. Its complexity is O(E log V) with a binary heap, making it faster than Kruskal for dense graphs. Prim’s is preferred when the graph is already stored as an adjacency list.

Topological Sort

Orders vertices in a directed acyclic graph (DAG) so that for every edge u → v, u comes before v.

def topological_sort(graph):
    visited = set()
    result = []

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        result.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)
    return result[::-1]

Applications: Build systems (Makefiles), course prerequisite scheduling, task scheduling, dependency resolution (package managers). Kahn’s algorithm provides an alternative using in-degree counting, which also detects cycles — if the sorted output contains fewer vertices than the input, the graph contains a cycle.

Advanced Graph Algorithms

Tarjan’s Algorithm (Strongly Connected Components)

Finds strongly connected components in O(V + E). Each SCC is a maximal set of vertices where every vertex is reachable from every other. Tarjan’s uses a single DFS with a low-link value to identify component roots. Used in compilers for dependency analysis, social network analysis to find tightly connected communities, and in web page ranking to identify link farms.

Floyd-Warshall Algorithm

Computes shortest paths between all pairs of vertices in O(V³). Essential for dense graphs where you need all-pairs shortest paths, such as in traffic routing systems. The algorithm is straightforward to implement with triple nested loops and can also detect negative cycles by checking whether any diagonal entry becomes negative.

Union-Find (Disjoint Set Union)

The union-find data structure supports efficient connectivity queries in dynamic graphs. With path compression and union by rank, amortized time per operation approaches O(α(n)) where α is the inverse Ackermann function. Union-find is used in Kruskal’s algorithm, image segmentation, and social network friend circle detection.

Maximum Flow (Ford-Fulkerson and Edmonds-Karp)

The maximum flow problem finds the maximum amount of flow that can be sent from a source to a sink in a flow network. Ford-Fulkerson uses augmenting paths in O(E × max_flow) time. Edmonds-Karp, which uses BFS to find the shortest augmenting path, achieves O(V × E²) time. Applications include bipartite matching, airline crew scheduling, and network bandwidth optimization. The min-cut max-flow theorem states that the maximum flow equals the minimum cut capacity, a result with deep implications in network reliability.

Choosing the Right Algorithm

Real-World Applications

Graph algorithms power countless systems. Social networks use BFS to suggest friends and detect communities. GPS navigation relies on Dijkstra and its variants (like A*) for real-time routing. Search engines use graph traversal to crawl and index web pages. Recommendation engines model user-item interactions as bipartite graphs. Compilers use topological sort for dependency resolution. Network infrastructure uses spanning trees to prevent broadcast storms. Biological networks use graph algorithms to analyze protein interactions and metabolic pathways. E-commerce platforms use bipartite matching for recommendation systems and A/B test assignment.

FAQ

What is the difference between BFS and DFS? BFS explores level by level using a queue and finds the shortest path in unweighted graphs. DFS explores depth-first using a stack or recursion and is better for topological sorting, cycle detection, and exploring the full structure. BFS requires more memory (O(width)) while DFS requires less (O(depth)) in sparse graphs.

When should I use Dijkstra versus Bellman-Ford? Use Dijkstra when all edge weights are non-negative — it is faster and simpler. Use Bellman-Ford when negative edge weights exist or when you need to detect negative cycles. Dijkstra may produce incorrect results with negative weights because it assumes earlier settled nodes have their final distances.

How do I detect cycles in a graph? For directed graphs, use DFS with a recursion stack — if you encounter a node already in the current recursion stack, a cycle exists. For undirected graphs, use DFS or union-find — if you encounter an already-visited node that is not the parent of the current node, a cycle exists.

What is the difference between Kruskal and Prim? Kruskal sorts all edges and adds the smallest non-cycle-forming edges — it works well for sparse graphs. Prim grows a tree from a start node by adding the minimum-weight edge connecting the tree to a new vertex — it works well for dense graphs. Kruskal uses union-find; Prim uses a priority queue.

How is A different from Dijkstra?* A* uses a heuristic function to guide the search toward the goal, making it faster in practice for point-to-point shortest path problems. Dijkstra explores equally in all directions. A* requires an admissible heuristic (never overestimates) for optimality. The better the heuristic, the fewer nodes A* explores.

Internal Links

Tree Data Structures — Searching Algorithms — Algorithm Design Patterns