Graph Algorithms

Breadth-First Search

from collections import deque

def bfs(graph: dict[int, list[int]], start: int) -> list[int]:
    visited = []
    queue = deque([start])
    seen = {start}
    while queue:
        node = queue.popleft()
        visited.append(node)
        for neighbour in graph.get(node, []):
            if neighbour not in seen:
                seen.add(neighbour)
                queue.append(neighbour)
    return visited

Dijkstra

import heapq

def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, int]:
    dist = {start: 0}
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist.get(node, float('inf')):
            continue
        for weight, neighbour in graph.get(node, []):
            nd = d + weight
            if nd < dist.get(neighbour, float('inf')):
                dist[neighbour] = nd
                heapq.heappush(heap, (nd, neighbour))
    return dist