Understanding Graph Algorithms: BFS, DFS, and Shortest Path

January 17, 2026 8 min read 0 Comments

Introduction to Graph Algorithms

Graph algorithms are fundamental to computer science and appear frequently in technical interviews and real-world applications. Understanding how to traverse and analyze graphs is essential for any software developer.

Graph Representation

Graphs can be represented using adjacency matrices or adjacency lists. An adjacency matrix uses a 2D array where matrix[i][j] = 1 if there's an edge from vertex i to j. An adjacency list uses an array of lists where each index stores the neighbors of that vertex.

# Adjacency List in Python
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

Breadth-First Search (BFS)

BFS explores a graph level by level, visiting all neighbors of a node before moving to the next level. It uses a queue data structure and is optimal for finding the shortest path in unweighted graphs.

from collections import deque

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

# Time: O(V + E), Space: O(V)

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It can be implemented recursively or iteratively using a stack. DFS is useful for detecting cycles, topological sorting, and finding connected components.

def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    result = [vertex]
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            result.extend(dfs_recursive(graph, neighbor, visited))
    return result

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            stack.extend(reversed(graph[vertex]))
    return result

Dijkstra's Shortest Path Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue to always process the vertex with the smallest distance.

import heapq

def dijkstra(graph, start):
    distances = {v: float('infinity') for v in graph}
    distances[start] = 0
    pq = [(0, start)]
    visited = set()
    while pq:
        dist, vertex = heapq.heappop(pq)
        if vertex in visited:
            continue
        visited.add(vertex)
        for neighbor, weight in graph[vertex].items():
            d = dist + weight
            if d < distances[neighbor]:
                distances[neighbor] = d
                heapq.heappush(pq, (d, neighbor))
    return distances

# Time: O((V+E) log V), Space: O(V)

Practical Applications

Graph algorithms power many real-world systems: social networks use BFS for friend recommendations, GPS navigation uses Dijkstra's for shortest routes, web crawlers use DFS for indexing, dependency resolution uses topological sort, and network routing protocols rely on shortest path algorithms.

Common Interview Problems

Practice these classic graph problems: number of islands, course schedule, network delay time, minimum spanning tree, detect cycle in directed/undirected graph, clone graph, and word ladder. Understanding graph fundamentals helps you tackle these efficiently.

DSA Python