Algorithm reference

Pseudocode, invariants and common pitfalls of each method in the studio, in the same notation used in class. This is exactly the formulation the simulation runs step by step.

Graph search

Depth-first search

Always picks the marked vertex that was reached most recently, recording a discovery time d and a finish time f.

O(n + m)

Core idea

A generic search in which, among all marked vertices incident to some unexplored edge, the one reached most recently is always chosen. Each vertex gets a discovery time d[v] and a finish time f[v], stamped by a global counter t.

Invariant

The lifetime intervals I(v) = [d[v], f[v]] are either nested or disjoint; they never partially overlap. Vertex w is a descendant of v if and only if I(w) is contained in I(v).

Graph requirements

Accepts directed and undirected edgesUndirected graph: tree and back edgesDirected graph: tree, back, forward and cross edges

Common pitfalls

In an undirected graph there are only tree and back edges; forward and cross edges appear only in directed graphs.
Forgetting the condition w ≠ parent[v]: the edge used to reach v is not a back edge.
Every back edge reveals a cycle in the original graph. In a directed graph, it is the only evidence needed.

Initialization / Initial call
  t ← 0
  for every vertex v ∈ V(G) do
    d[v] ← 0; f[v] ← 0; parent[v] ← null
  while there is some vertex v such that d[v] = 0 do
    Run Depth_Search(v)              // v is the search root
 
Depth_Search(v)                       // undirected graph
  t ← t + 1; d[v] ← t
  for every vertex w ∈ Γ(v) do
    if d[w] = 0 then                 // tree edge
      parent[w] ← v; Run Depth_Search(w)
    else if f[w] = 0 and w ≠ parent[v] then
      Visit back edge {v, w}
  t ← t + 1; f[v] ← t
 
Depth_Search(v)                       // directed graph
  for every vertex w ∈ Γ⁺(v) do
    if d[w] = 0 then  tree edge (v, w); parent[w] ← v; ...
    else if f[w] = 0 then             back edge (v, w)
    else if d[v] < d[w] then          forward edge (v, w)
    else                              cross edge (v, w)

Graph search

Breadth-first search

Always picks the marked vertex that was reached least recently, using a queue, and assigns each vertex its level.

O(n + m)

Core idea

A generic search in which, among all marked vertices incident to some unexplored edge, the one reached least recently is always chosen, a rule implemented with a queue. Each vertex gets an index L[v] (discovery order) and a level[v] (distance from the root in number of edges).

Invariant

level[w] = level[parent[w]] + 1 for every w ≠ root. So, as soon as w is marked, level[w] is already the distance (number of edges) between the search root and w.

Graph requirements

Accepts directed and undirected edgesIgnores edge weightsClassifies edges as parent, uncle, sibling and cousin

Common pitfalls

Marking the vertex (assigning L[w]) only when it leaves the queue, not when it enters: the same vertex would end up queued several times.
Forgetting the condition L[w] > L[v] when classifying sibling and cousin edges: it guarantees that each edge is explored only once.
In a weighted graph, breadth-first search only returns a minimum-weight path if all weights are equal; it minimizes the number of edges, not the weight.

Initialization / Initial call
  t ← 0; Queue ← ∅
  for every vertex v ∈ V(G) do
    L[v] ← 0; level[v] ← 0; parent[v] ← null
  while there is some vertex v such that L[v] = 0 do
    t ← t + 1; L[v] ← t          // v is the search root
    Queue.Insert(v)
    Run Breadth_Search()
 
Breadth_Search()
  while not Queue.Empty() do
    v ← Queue.Remove()
    for every vertex w ∈ Γ(v) do
      if L[w] = 0 then           // tree (or parent) edge
        parent[w] ← v; level[w] ← level[v] + 1
        t ← t + 1; L[w] ← t; Queue.Insert(w)
      else if level[w] = level[v] + 1 then
        Visit uncle edge {v, w}
      else if level[w] = level[v] and parent[v] = parent[w] and L[w] > L[v] then
        Visit sibling edge {v, w}
      else if level[w] = level[v] and parent[v] ≠ parent[w] and L[w] > L[v] then
        Visit cousin edge {v, w}

Connectivity

Kosaraju's algorithm

Finds the strongly connected components with two depth-first searches: one on G and another on the reverse graph Gᴿ.

O(n + m)

Core idea

A first depth-first search on G records the finish times f. The second search, run on the reverse graph Gᴿ and taking vertices in decreasing order of f, produces a forest in which each tree is exactly one strongly connected component.

Invariant

The decreasing order of finish times guarantees that the search on Gᴿ started at a vertex never escapes the strongly connected component it belongs to.

Graph requirements

Requires a directed graphIgnores edge weights

Common pitfalls

Forgetting to build the reverse graph Gᴿ before the second search.
Running the second search in increasing order of f instead of decreasing order.
Mixing up the three levels of connectivity of a connected directed graph: weakly connected (the underlying graph is connected), unilaterally connected (for every pair, one reaches the other) and strongly connected (all mutually reachable).

Kosaraju's algorithm
  1. Run a depth-first search on G
       // store the finish time f of every vertex
  2. Build the reverse (or transpose) graph Gᴿ
       // if (v, w) ∈ E(G) then (w, v) ∈ E(Gᴿ)
  3. Run a depth-first search on Gᴿ taking the vertices
     in decreasing order of f
 
  Each tree of the depth-first forest obtained in step 3
  corresponds to a strongly connected component of G.

Eulerian graphs

Fleury's algorithm

Builds an Eulerian trail by walking through the graph and avoiding crossing a bridge while another edge is still available.

O(m² )

Core idea

A connected graph is Eulerian if and only if all of its vertices have even degree (Euler's theorem), and semi-Eulerian if exactly two vertices have odd degree. The algorithm walks through the graph removing the traversed edges and avoids crossing a bridge while there is another option.

Invariant

The trail being built never repeats edges and, by avoiding bridges, keeps the remaining edges of G' connected, which guarantees that the walk only ends once every edge has been traversed.

Graph requirements

Requires an undirected, connected graphAt most 2 vertices of odd degreeIgnores edge weights

Common pitfalls

Crossing a bridge while another edge is available: the edges on the other side become unreachable and the trail ends early.
Starting from a vertex of even degree in a semi-Eulerian graph: the trail must start at one of the two vertices of odd degree.
Confusing it with a Hamiltonian graph: an Eulerian trail uses each edge once, a Hamiltonian path visits each vertex once.

Fleury's algorithm
  1. if V(G) has 3 or more vertices of odd degree then STOP
  2. Let G' = (V', E') such that V' ← V(G) and E' ← E(G)
  3. Select a starting vertex v ∈ V'
       (choose a vertex v of odd degree, if there is one)
  4. while E' ≠ ∅ do
     a. if d(v) > 1 then
          Select an edge {v, w} that is not a bridge in G'
        else
          Select the only edge {v, w} available in G'
     c. v ← w;   E' ← E' − {v, w}
 
  // Walk from v to w and remove the traversed edge

Minimum spanning tree

Prim's algorithm

Adds vertices one by one: at each step it takes the lightest edge between V(T) and the vertices not yet selected.

O(m log n)

Core idea

Builds the MST greedily by adding vertices one at a time. Starting from a root r, at each step it adds the lightest edge with one endpoint in V(T) (already selected) and the other outside V(T).

Invariant

At every iteration, T = (V(T), E(T)) is a tree and is contained in some minimum spanning tree of G.

Graph requirements

Requires an undirected graphRequires a weighted graph with w(e) > 0A spanning tree only exists if the graph is connected

Common pitfalls

Comparing the edge weight with the accumulated distance from the root instead of the edge's own weight, which would turn Prim into Dijkstra.
Applying Prim to a directed graph: the correct problem then becomes the minimum-weight arborescence.
A disconnected graph has no spanning tree: a graph G has a spanning tree if and only if G is connected.

Prim's algorithm
  1. Choose any vertex r ∈ V(G)              // root
  2. V(T) ← { r }        // set of selected vertices
  3. E(T) ← ∅            // set of MST edges
  4. while V(T) ≠ V(G) do
     a. Find the lightest edge {v, w} such that
        v ∈ V(T) and w ∉ V(T)
     b. Add w to V(T)
     c. Add {v, w} to E(T)
 
  Total weight: C(T) = Σ  w  , for e ∈ E(T)
                           e

Minimum spanning tree

Kruskal's algorithm

Adds edges, not vertices: sorts the edges by non-decreasing weight and accepts each one that does not form a cycle with those already in E(T).

O(m log m)

Core idea

Builds the MST by adding edges, not vertices as in Prim. It sorts the edges in non-decreasing order of weight and, at each iteration, accepts the lightest edge that does not form a cycle with those already in E(T).

Invariant

At every iteration, T = (V(T), E(T)) is a spanning forest contained in some minimum spanning tree of G.

Graph requirements

Requires an undirected graphRequires a weighted graph with w(e) > 0On a disconnected graph it produces a minimum spanning forest

Common pitfalls

Assuming that n − 1 iterations are enough: at least n − 1 are needed, but there may be more, since edges that form a cycle have to be skipped.
Accepting an edge whose endpoints are already connected by edges of E(T): it would close a cycle.
On a disconnected graph the result is a minimum spanning forest, not a spanning tree.

Kruskal's algorithm
  1. Sort the edges in non-decreasing order of weight:
     e₁, e₂, e₃, . . .
  2. V(T) ← V(G)      // every vertex joins the MST
  3. E(T) ← { e₁ }
  4. j ← 2            // edge to be examined
  5. while | E(T) | < | V(T) | − 1 do
     a. if the edge e  does not form a cycle with the edges of E(T)
                     j
        then Add e  to E(T)
                  j
     b. j ← j + 1

Shortest paths

Dijkstra's algorithm

"Closes" one vertex per iteration, always the one with the smallest dist, and relaxes the tense edges leaving it.

O(n²)

Core idea

Solves the single-source shortest path problem from a root s. It relies on the relaxation principle and "closes" one vertex per iteration: it picks the not yet closed vertex with the smallest dist value and relaxes the tense edges leaving it.

Invariant

For every v ∈ S, dist[v] is already the weight of the shortest path from the root to v. At the end, dist[ ] holds the weights of the shortest paths; the paths themselves are recovered through the predecessor list pred[ ].

Graph requirements

Accepts directed and undirected edgesRequires non-negative weightsBased on the relaxation principle

Common pitfalls

Running the algorithm on a graph with a negative-weight edge: it fails. Reweighting by adding a constant to every edge can fail too.
Reopening a vertex that already belongs to S: once closed, its dist never changes again.
Assuming dist[ ] returns the paths: without pred[ ] you only get the weights.

Relaxation step
  if dist[v] + d    < dist[w] then    // is edge (v, w) tense?
                vw
    dist[w] ← dist[v] + d
                         vw
    pred[w] ← v
 
Dijkstra's algorithm
  1. for every vertex v ∈ V(G) do
       dist[v] ← ∞; pred[v] ← null
  2. dist[s] ← 0        // s is the search root
  3. S ← ∅              // set of closed vertices
  4. while S ≠ V(G) do
     a. Choose the vertex v ∉ S with the smallest dist[v]
     b. S ← S ∪ { v }                  // "close" vertex v
     c. for every vertex w ∈ Γ⁺(v) do
          if dist[w] > dist[v] + d    then    // tense edge?
                                  vw
            dist[w] ← dist[v] + d
                                 vw
            pred[w] ← v

Shortest paths

Bellman-Ford algorithm

Dynamic programming: examines every edge in each iteration, relaxing the tense ones, for |V(G)| − 1 iterations.

O(n · m)

Core idea

Computes shortest paths through dynamic programming. Instead of "closing" one vertex per iteration, as Dijkstra does, it examines every edge in each iteration. Since any path in a graph with n vertices has at most n − 1 edges, n − 1 iterations are enough.

Invariant

After the i-th iteration, dist[w] is at most the weight of the shortest path from s to w that uses up to i edges.

Graph requirements

Allows negative-weight edgesDoes not allow negative-weight cyclesDetects a negative-weight cycle reachable from the source

Common pitfalls

If no edge is tense in some iteration, the algorithm can stop: the following iterations would bring no updates.
If there is a negative-weight cycle between s and t, no shortest path exists between them; without such a cycle, the shortest path is simple (it does not repeat vertices).
An undirected edge with negative weight is, by itself, a negative-weight cycle.

Relaxation step
  if dist[v] + d    < dist[w] then    // is edge (v, w) tense?
                vw
    dist[w] ← dist[v] + d
                         vw
    pred[w] ← v
 
Bellman-Ford algorithm
  1. for every vertex v ∈ V(G) do
       dist[v] ← ∞; pred[v] ← null
  2. dist[s] ← 0
  3. for i = 1, . . ., | V(G) | − 1 do
       for each (v, w) ∈ E(G) do
         if dist[w] > dist[v] + d    then    // tense edge?
                                 vw
           dist[w] ← dist[v] + d
                                vw
           pred[w] ← v
 
  If some edge is still tense after the last iteration,
  then the graph has a negative-weight cycle.

Shortest paths

Floyd-Warshall algorithm

All-pairs shortest paths through dynamic programming: round k allows vertex k as an intermediate.

O(n³)

Core idea

Dynamic programming over the set of allowed intermediate vertices. With the vertices numbered from 1 to n, distᵏ[i, j] is the distance between i and j using only vertices of { 1, 2, . . ., k } as intermediates.

Invariant

At the end of round k, dist[i, j] is the weight of the shortest path from i to j that uses only { 1, . . ., k } as intermediate vertices; pred[i, j] stores the second-to-last vertex of that path.

Graph requirements

Allows negative-weight edgesDoes not allow negative-weight cyclesComputes every pair of vertices at once

Common pitfalls

Swapping the loop order: k must be the outermost loop.
Updating the predecessor with pred[i, k] instead of pred[k, j]: pred[i, j] is the second-to-last vertex of the path from i to j.
A negative entry on the diagonal, that is, dist[i, i] < 0, indicates a negative-weight cycle.

Path length relaxation
  distᵏ[i, j] = min( distᵏ⁻¹[i, j],
                     distᵏ⁻¹[i, k] + distᵏ⁻¹[k, j] )
  with dist⁰[i, j] = d   if (i, j) ∈ E(G); ∞ otherwise;
                      ij
  and dist⁰[i, i] = 0
 
Floyd-Warshall algorithm
  1. for i = 1, . . ., n do
       for j = 1, . . ., n | j ≠ i do
         dist[i, j] ← ∞; pred[i, j] ← null
       dist[i, i] ← 0;   pred[i, i] ← i
  2. for every edge (i, j) ∈ E(G) do
       dist[i, j] ← d  ;  pred[i, j] ← i
                     ij
  3. for k = 1, . . ., n do     // each possible intermediate
       for i = 1, . . ., n do
         for j = 1, . . ., n do
           if dist[i, j] > dist[i, k] + dist[k, j] then
             dist[i, j] ← dist[i, k] + dist[k, j]
             pred[i, j] ← pred[k, j]

Maximum flow

Ford-Fulkerson method

While some augmenting path exists in G'(f), pushes the bottleneck δ along it and updates the residual network.

O(m · f) with integer capacities

Core idea

While there is an augmenting path from the source s to the sink t in the residual network G′(f), push as much as possible along it, the bottleneck δ, and update the residual network. Backward edges allow earlier pushes to be undone.

Invariant

The flow f always satisfies the capacity constraint, 0 ≤ f(e) ≤ u(e), and flow conservation at every internal node. By the max-flow min-cut theorem, at the end the flow value equals the capacity of the minimum s-t cut.

Graph requirements

Requires a flow network: a directed graph with capacity u(e) > 0Requires a source s and a sink tThe augmenting path is chosen arbitrarily

Common pitfalls

Forgetting to create the backward edge in the residual network, which prevents undoing pushes made in earlier iterations.
Choosing arbitrary augmenting paths: with irrational capacities the method may never terminate. Always choosing the augmenting path with the fewest edges (breadth-first search) is the Edmonds-Karp algorithm.
Assuming the minimum cut is any cut: in the optimal solution, S is the set of vertices reachable from the source s in the final residual network.

Residual network G′(f): V(G′) = V(G) and, for e = (v, w) ∈ E:
  if f(e) < u(e): forward edge (v, w) with u (e) = u(e) − f(e)
                                            r
  if f(e) > 0:    backward edge (w, v) with capacity f(e)
 
Ford-Fulkerson method
  1. for every edge e ∈ E(G) do  f(e) ← 0
  2. Build the residual network G′(f)
  3. while there is an augmenting path P in G′(f) do
     a. δ ← min { u (e) | e ∈ P }        // "bottleneck" of P
                   r
     b. for each edge (v, w) ∈ P do
        i.  if (v, w) is a forward edge then
              f(v, w) ← f(v, w) + δ      // increase flow
        ii. else
              f(w, v) ← f(w, v) − δ      // decrease flow
     c. Update the residual network G′(f)

Maximum flow

Edmonds-Karp algorithm

An efficient implementation of Ford-Fulkerson: each iteration picks the shortest augmenting path, found by breadth-first search.

O(n · m² )

Core idea

An efficient implementation of the Ford-Fulkerson method: each iteration selects the shortest augmenting path in the residual network, that is, the one with the fewest edges. That path is found with a breadth-first search.

Invariant

The length of the chosen augmenting path never decreases from one iteration to the next. There are at most O(n·m) augmenting paths and each is found in O(m), hence O(n·m²).

Graph requirements

Requires a flow network: a directed graph with capacity u(e) > 0Requires a source s and a sink tAlways picks the augmenting path with the fewest edges

Common pitfalls

Using depth-first search: you are back to the generic Ford-Fulkerson method, which is only pseudo-polynomial, O(m·f), with f equal to the maximum flow value.
In the network with two edges of capacity 100 joined by one of capacity 1, an arbitrary choice may require 200 iterations; choosing the shortest path requires 2.
Forgetting that the algorithm was published independently by Dinitz (1970) and by Edmonds and Karp (1972).

Edmonds-Karp algorithm
  1. for every edge e ∈ E(G) do  f(e) ← 0
  2. Build the residual network G′(f)
  3. while there is some augmenting path P in G′(f) do
     a. Let P be the augmenting path in G′(f) with the fewest
        edges   // found by breadth-first search
     b. δ ← min { u (e) | e ∈ P }
                   r
     c. for each edge (v, w) ∈ P do
        i.  if (v, w) is a forward edge then
              f(v, w) ← f(v, w) + δ
        ii. else
              f(w, v) ← f(w, v) − δ
     d. Update the residual network G′(f)

Maximum flow

Dinic's algorithm

Each iteration builds the level graph GL from G′(f) and finds a blocking flow in it.

O(n² · m)

Core idea

Instead of augmenting one path at a time, it builds the level graph GL from G′(f) and finds a full blocking flow in it. Since the number of levels grows by at least one at each iteration, there are at most n − 1 blocking flows.

Invariant

dist(t) strictly increases between iterations, so there are at most n − 1 blocking flows. Each blocking flow is found in O(n·m), hence O(n²·m).

Graph requirements

Requires a flow network: a directed graph with capacity u(e) > 0Requires a source s and a sink tAt most n − 1 blocking flows

Common pitfalls

Searching for paths outside GL: only edges (v, w) with dist(w) = dist(v) + 1 count.
Rebuilding the level graph after every path instead of after every blocking flow: an iteration is defined by the complete blocking flow.
Stopping as soon as one path saturates: the blocking flow only ends when there is no path left from s to t in GL.

Level graph GL: V(GL) = V(G′) and, for (v, w) ∈ E(G′):
  (v, w) ∈ E(GL) with capacity u (e) if dist(w) = dist(v) + 1,
                                r
  where dist(v) is the shortest geodesic distance from s to v
 
Blocking flow fb: a flow in GL such that, keeping only the
  edges with capacity greater than fb, there is no longer
  any augmenting path in GL
 
Dinic's algorithm
  1. for every edge e ∈ E(G) do  f(e) ← 0
  2. Build the residual network G′(f)
  3. Build the level graph GL from G′(f)
  4. while dist(t) < ∞ do
     a. Find a blocking flow fb in GL
     b. Update the flow f using fb
     c. Update the residual network G′(f)
     d. Build the level graph GL from G′(f)

Topological sorting

Kahn's algorithm

At each step takes a vertex with in-degree zero, appends it to the result and lowers the in-degree of its successors.

O(n + m)

Core idea

At each step it finds a vertex with no incoming edges, that is, with d⁻(v) = 0, and appends it to the end of the result. Instead of removing edges, it keeps and updates a map M with the in-degree of each vertex.

Invariant

A vertex only enters the queue once all of its predecessors are already in Topo_Order, so ord(v) < ord(w) for every edge (v, w) ∈ E(G).

Graph requirements

Requires a directed graphA topological order only exists in an acyclic graphDetects the presence of a cycle

Common pitfalls

Applying it to an undirected graph or to a graph with a cycle: no precedence relation can be established, and no topological order exists.
Treating an empty queue with pending vertices as an error: that is exactly how the algorithm detects a cycle.
Assuming the order is unique: a directed acyclic graph can have several valid topological orders.

Kahn's algorithm
  1. for every vertex v do M[v] ← d⁻(v)
  2. Queue ← ∅; Topo_Order ← ∅
  3. for every vertex v such that d⁻(v) = 0 do
       Queue.Insert(v)
  4. while not Queue.Empty() do
     a. v ← Queue.Remove()
     b. Topo_Order.InsertAtEnd(v)
     c. for every vertex w ∈ Γ⁺(v) do
        i.  M[w] ← M[w] − 1
        ii. if M[w] = 0 then Queue.Insert(w)
  5. If every vertex was processed, SUCCESS;
     otherwise, there is a CYCLE

Topological sorting

Topological sort via depth-first search

Described by Tarjan in 1976: inserts each vertex at the front of the result only after visiting every vertex that depends on it.

O(n + m)

Core idea

An alternative based on depth-first search, described by Tarjan in 1976. Each vertex is inserted into the result only after every vertex that depends on it, and insertion happens at the front of the list, hence the reverse order.

Invariant

When v receives its permanent mark, every vertex reachable from v is already in Topo_Order. Since v is inserted at the front, it precedes all of them in the order.

Graph requirements

Requires a directed graphA topological order only exists in an acyclic graphMeeting a temporary mark again reveals a cycle

Common pitfalls

Inserting at the end instead of the front: the order comes out reversed. The correct order is the reverse of the insertion order, equivalent to decreasing order of finish time.
Not distinguishing temporary from permanent marks: only meeting a temporary mark again reveals a cycle; a permanent mark indicates a vertex already resolved.
Confusing it with the ordinary depth-first forest: what matters here is the finishing order, not the tree.

Depth-first search method
  1. for every vertex v do Mark[v] ← 0
  2. Topo_Order ← ∅
  3. while there is some vertex v such that Mark[v] = 0
     do Visit(v)
 
Visit(v)
  1. if Mark[v] ≠ 2 then        // if v is not permanent
     a. if Mark[v] = 1 then CYCLE     // temporary mark
     b. Mark[v] ← 1                   // temporary mark
     c. for every vertex w ∈ Γ⁺(v) do Visit(w)
     d. Mark[v] ← 2                   // permanent mark
     e. Topo_Order.InsertAtFront(v)

Matching

Edmonds' blossom algorithm

Searches for M-augmenting paths between exposed vertices, contracting the blossoms that appear, until none is left.

O(n² · m)

Core idea

By Berge's theorem, M has maximum cardinality if and only if there is no M-augmenting path. The algorithm looks for such paths in an M-alternating forest; when an edge joins two vertices at even distance in the same tree, an odd cycle appears, the blossom, which is contracted into a pseudo-vertex.

Invariant

M ⊕ EP is always a matching with one more edge than M. By Edmonds' theorem, M is maximum in G if and only if M/B is maximum in G/B, which justifies contracting blossoms.

Graph requirements

Requires an undirected graphIgnores edge weightsHandles general graphs, not only bipartite ones

Common pitfalls

Using plain breadth-first or depth-first search on a general graph: without handling blossoms, existing M-augmenting paths go unnoticed.
Ignoring the edge {v, w} when dist(w, F.root[w]) is odd: it does not produce an augmenting path.
Confusing a maximal matching with a maximum one: maximal only means no edge can be added; maximum is the one with the largest cardinality. And a maximum matching does not imply a perfect matching.

Maximum_Matching(G)
  1. M ← ∅
  2. P ← Find_Augmenting_Path(G, M)
  3. while (P ≠ ∅) do
     a. M ← M ⊕ EP
     b. P ← Find_Augmenting_Path(G, M)
 
Find_Augmenting_Path(G, M)
  1. F ← Init_Alternating_Forest(G, M)
  2. for every unmarked vertex v ∈ F such that
     dist(v, F.root[v]) is even do
     a. while ∃ unmarked edge e = {v, w} do
        i.   if w ∉ F then Add_To_Forest(M, F, v, w)
        ii.  else if dist(w, F.root[w]) is even then
               return Get_New_Path(G, M, F, v, w)
        iii. Mark edge e
     b. Mark vertex v
  3. return ∅
 
Get_New_Path(G, M, F, v, w)
  1. if F.root[v] ≠ F.root[w] then
       P ← GetPath(F, F.root[v], v)
            + GetPath(F, w, F.root[w])
  2. else                            // blossom
     a. B ← GetPath(F, v, w) + v
     b. G′ ← Contract_Blossom_Graph(G, B, z)
     c. M′ ← Contract_Blossom_Matching(M, B, z)
     d. P ← Find_Augmenting_Path(G′, M′)
     e. if z ∈ P then P ← Expand_Blossom(P, G, B, z)
  3. return P

Coloring

Greedy coloring

Goes through the vertices in any order and gives each one the lowest-index color not used by any of its neighbors.

O(n + m)

Core idea

There is no efficient method to find the minimum coloring of a graph, but an approximate coloring can be found quickly: go through the vertices in any order, giving each one the lowest-index color not used by its neighbors.

Invariant

At every step the partial coloring is valid: color(v) ≠ color(w) for every pair of adjacent colored vertices. Since a vertex has at most Δ(G) neighbors, the method never uses more than Δ(G) + 1 colors.

Graph requirements

Requires an undirected graphApproximate coloring, not necessarily minimumThe result depends on the vertex order

Common pitfalls

Taking the number of colors obtained as the chromatic number: the result depends on the vertex order and χ(G) is usually smaller.
Forgetting the known bounds: ω(G) ≤ χ(G) ≤ Δ(G) + 1 and, by Brooks' theorem, χ(G) ≤ Δ(G) if G is simple, not complete and not an odd cycle.
Applying it to a directed graph: vertex coloring is defined for undirected graphs.

Greedy method
  1. Consider the vertices of the graph in any order
     v₁, v₂, . . ., vₙ
  2. Identify the colors by indices, adding more colors
     when needed
  3. Color v₁ with the first color
  4. At each iteration, give the current vertex the
     lowest-index color not used by any of its neighbors

Coloring

Welsh-Powell algorithm

Sorts the vertices by non-increasing degree and gives one color to every vertex not adjacent to a vertex already painted with it.

O(n² )

Core idea

A refinement of the greedy method: the vertices are sorted by non-increasing degree and each color is handed out in a full pass through the list, coloring every vertex that is not adjacent to one already painted with that color.

Invariant

Each color forms an independent set: no two vertices with the same color are adjacent. The method terminates because each pass colors at least one vertex.

Graph requirements

Requires an undirected graphApproximate coloring, not necessarily minimumUsually uses fewer colors than the greedy method

Common pitfalls

Taking the result as optimal: there is a counterexample in which Welsh-Powell uses 3 colors on a bipartite graph, for which χ(G) = 2.
Dropping the degree order when starting a new color: the sorted list is walked from the beginning in every pass.
Coloring a vertex adjacent to another already painted with the current pass color: the check is against the vertices already painted with that color.

Welsh-Powell algorithm
  1. Sort the vertices by non-increasing degree
     v₁, v₂, . . ., vₙ
  2. Identify the colors by indices, adding more colors
     when needed
  3. Color v₁ with the first color
  4. Go down the vertex list coloring every vertex that is
     not adjacent to an already colored vertex, always using
     the same color
  5. Repeat step 4 for every uncolored vertex using a new
     color, always following the non-increasing degree
     order, until every vertex is colored