Graph Algorithms

Two algorithms you'll use constantly once you're past basic traversal:

Shortest path in an unweighted graph is just BFS with a distance counter — since BFS explores level by level, the first time you reach a node IS the shortest path to it, in number of edges.

from collections import deque

def shortest_path_length(graph, start, end):
    if start == end:
        return 0
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == end:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1

Topological sort orders the nodes of a DAG (Directed Acyclic Graph) so that every edge points from earlier to later in the ordering — "finish task A before starting task B" scheduling, or resolving package/import dependencies. A DFS-based approach: run DFS from every unvisited node, and each node is added to the front of the result only after ALL of its descendants have already been added (a post-order DFS, reversed).

def topological_sort(graph):
    visited = set()
    order = []
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        order.append(node)
    for node in graph:
        if node not in visited:
            dfs(node)
    return order[::-1]

If the graph has a cycle, no valid ordering exists — topological sort is only defined for DAGs.