breadth first search

Last edited: December 12, 2025

L = [[start_node]]+[[] for _ in 1 ... n]
start_node.visited = True

for i = 0 ... n-1:
    for u in L[i]:
        for v in neighbor(u):
            if not v.visited:
                v.visited = True
                L[i+1].append(v)

This uses \(O\qty(n+m)\). We can find the shortest paths in \(O\qty(m)\)

minimum cut and maximum flow

Last edited: December 12, 2025

Setup: graphs are directed, and edges have “capacities”. We have source vertex \(s\) and sink vertex \(t\).

definitions

s-t cut

A cut is a s-t cuts is for a directed graph it goes from s’s side to t’s side; an edge cross an s-t cuts is the edges that goes from \(s\)’s side to \(t’s\) side