Graph Algorithms: BFS, DFS, Dijkstra and Topological Sort

Graph Algorithms

Graphs model networks, relationships, dependencies, and maps. BFS, DFS, and Dijkstra's algorithm are the three most important graph algorithms for coding interviews at every level.

from collections import defaultdict, deque
import heapq

# Graph representation: adjacency list
graph = defaultdict(list)
edges = [(0,1),(0,2),(1,3),(2,3),(3,4)]
for u,v in edges:
    graph[u].append(v)
    graph[v].append(u)  # undirected

# BFS — shortest path in unweighted graph
def bfs(graph, start, end):
    visited = {start}
    queue   = deque([(start, [start])])  # (node, path)
    while queue:
        node, path = queue.popleft()
        if node == end: return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None

print(bfs(graph, 0, 4))  # [0, 1, 3, 4] or [0, 2, 3, 4]

# DFS — detect cycles, connected components
def dfs(graph, start, visited=None, path=None):
    if visited is None: visited = set()
    if path    is None: path    = []
    visited.add(start)
    path.append(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, path)
    return path

# Dijkstra — shortest path in weighted graph
def dijkstra(graph, start):
    dist = {start: 0}
    heap = [(0, start)]  # (distance, node)
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist.get(node, float('inf')): continue
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist.get(neighbor, float('inf')):
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return dist

Topological Sort

def topo_sort(graph, nodes):
    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 nodes:
        if node not in visited:
            dfs(node)

    return result[::-1]  # reverse post-order

# Use case: course prerequisite order, build systems, task dependencies