2 Basics, Notation and Data Structures

BFS-Components

Finds connected components in a graph using iterated Breadth-First-Search (BFS).

DFS Recursive

A recursive implementation of Depth-First-Search (DFS), which computes a DFS labeling.

Iterative BFS

An iterative implementation of Breadth-First-Search (BFS), which computes a BFS labeling.

BFS to DFS

Converting the iterative BFS implementation to an iterative DFS implementation by exchanging the Queue for a Stack.

Iterative DFS

An iterative implementation of Depth-First-Search (DFS), which computes a DFS labeling.

3 Minimum Spanning Trees

Kruskal's Algorithm

Kruskal's algorithm computes a minimum spanning tree in a connected, weighted graph.

Kruskal's Algorithm using FindCircuit

A more detailed, but naive implementation of Kruskal's algorithm, which checks for each edge to be added whether it completes a circuit.

Inefficient Kruskal's Algorithm

An improved, but still somewhat naive implementation of Kruskal's algorithm, which bypasses the explicit test for circuit completion by maintaining component labels for vertices and testing for equality.

Efficient Kruskal's Algorithm

An efficient implementation of Kruskal's algorithm, which minimizes the number of component label updates.

Prim's Algorithm

Prim's Algorithm computes a minimum spanning tree in a connected, weighted graph.

Matroid Dual of Kruskal's Algorithm

An implementation of a matroid dual of Kruskal's Algorithm.

4 Linear Programming Duality

Primal Dual of Kruskal's Algorithm

A primal dual version of Kruskal's Algorithm.

5 Shortest Paths

Dijkstra's Algorithm

Dijkstra's algorithm for finding a shortest path tree in a graph. This is an example of a label setting algorithm.

Dijkstra's Algorithm using a Priority Queue

Dijkstra's algorithm for finding a shortest path tree in a graph implemented using a Priority Queue.

Find Path

A variant of Dijkstra's algorithm for finding a shortest s-t path in a graph. Terminates early, as soon as a shortest s-t path has been found.

Find Path in an Euclidean Graph

A variant of Dijkstra's algorithm for finding a shortest s-t path in an Euclidean graph (edge weights correspond to Euclidean distance between vertices). Terminates early, as soon as a shortest s-t path has been found and only visits a small part of the graph. Similar ideas are used in A*-type algorithms.

Bellman Ford

Bellman and Ford's algorithm for finding a shortest path tree in a graph with a label correcting approach.

Finding Negative Circuits

Most shortest path algorithms require that graphs do not have negative circuits. This algorithms detects negative circuits in a graph.

Find Path from Two Sources

Finding a path can be accelerated by searching from start and destination simultaneously.

6 Maximal Flows

The Ford-Fulkerson Algorithm

The Ford-Fulkerson algorithm finds a maximal flow in a capacitated network by successive shortest path applications.

Preflow Push

The Preflow Push algorithm due to Goldberg and Tarjan computes a maximal flow by saturating a network and correcting possible excesses later.

7 Minimum-Cost Flows

Negative Cycle Canceling

The Negative Cycle Canceling algorithm establishes a maximal flow and reduces costs by finding negative circuits.

Successive Shortest Paths

This algorithm finds a minimum cost flow by repeatedly finding shortest, augmenting paths.

Cost Scaling

The cost scaling algorithm directly operates on the bits of the cost function.

8 Matching

Bipartite

This algorithm finds a maximal cardinality matching in a bipartite graph. In other words it maximizes the number of matched vertices.

Cardinality Matching

This algorithm finds a maximal cardinality matching in graphs which are not necessarily bipartite.

9 Weighted Matching

Weighted Matching

This algorithm considers vertices as points in 2-dimensional space and implicitly assumes the existence of all edges in the complete graph. Furthermore, edge weights are Euclidean. It finds a matching of minimal weight. The matching is perfect if the number of vertices is even