Graph Algorithms Cheat Sheet

from collections import defaultdictgraph = defaultdict(list)graph[0].append(1)   # edge 0 -> 1graph[1].append(2)graph[0].append(2)# Weighted graph: store (neighbor, weight) tuplesweighted = defaultdict(list)weighted[0].append((1, 4))  # edge 0->1 with weight 4weighted[1].append((2, 2))

from collections import dequedef bfs(graph, start):    visited, queue, order = {start}, deque([start]), []    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 orderdef dfs(graph, start):    visited, stack, order = set(), [start], []    while stack:        node = stack.pop()        if node not in visited:            visited.add(node)            order.append(node)            stack.extend(graph[node])    return order

import heapqdef dijkstra(graph, start):    dist = {start: 0}    pq = [(0, start)]    while pq:        d, node = heapq.heappop(pq)        if d > dist.get(node, float('inf')):            continue        for neighbor, weight in graph[node]:            nd = d + weight            if nd < dist.get(neighbor, float('inf')):                dist[neighbor] = nd                heapq.heappush(pq, (nd, neighbor))    return dist