Depth First Search

Flood Fill - Grid

H and W is the height of the grid and the width of the grid respectively.

grid[x][y] stores the grid information for the cell (x, y) where 0 ≤ x < H and 0 ≤ y < W. A cell with 'X' will mean it is a restricted cell (cannot travel on it).

visited[x][y] indicates whether the cell (x, y) has been visited by DFS before

Flood Fill - Adj List

Nodes are labelled from 0 to N-1 and adjList[x] stores the directed edges that points from node x to other notes.

visited[x] indicates whether the node x has been visited or not.

Topological Sort

Nodes are labelled from 0 to N-1 and adjList[x] stores the directed edges that points from node x to other notes.

visited[x] indicates whether the node x has been visited or not.

Topological order will be stored in vector topo.

SSSP on Tree

Nodes are labelled from 0 to N-1 and adjList[x] stores the directed edges that points from node x to other notes.

S will be the source of the algorithm. Distance from S to X will be located at dist[X]. A distance of -1 indicates that it is not possible to reach node X from S

Breadth First Search

SSSP on Grid

For BFS to work for SSSP, edge weights must be the same (or 1).

H and W is the height of the grid and the width of the grid respectively.

grid[x][y] stores the grid information for the cell (x, y) where 0 ≤ x < H and 0 ≤ y < W. A cell with 'X' will mean it is a restricted cell (cannot travel on it).

dist[x][y] indicates the distance from the start cell(sx, sy) to the cell (x, y). If it is -1, it means that cell (x, y) is not reachable from the start cell.

SSSP on AdjList

For BFS to work for SSSP, edge weights must be the same (or 1).

Nodes are labelled from 0 to N-1 and adjList[x] stores the directed edges that points from node x to other notes.

dist[x] indicates the distance from the start node S to node x

Floyd Warshall

The following floyd warshall code works for non-negative edge weights only.

Nodes are labelled from 0 to N-1 and adjMat[x][y] stores the edge weight from node x to node y. If there is no edge from node x to node y, set adjMat[x][y] to -1 instead.

Shortest Path Faster Algorithm

Normal SPFA

Use this code only when the end isn't provided by the problem (or you need distance to all the nodes)

Nodes are labelled from 0 to N-1 and adjList[x] stores the directed edges that points from node x to other notes.

Source is defined as node S.

dist[x] indicates the distance from the start node S to node x

Pruned SPFA

Use this code when the end is provided for significant pruning (lower runtime)

Nodes are labelled from 0 to N-1 and adjList[x] stores the directed edges that points from node x to other notes.

Source is defined as node S and the End is defined as node E

Dijkstra

Nodes are labelled from 0 to N-1 and adjList[x] stores the directed edges that points from node x to other notes.

Source is defined as node S.

dist[x] indicates the distance from the start node S to node x

Kruskal

Nodes are labelled from 0 to N-1 and edgeList stores the list of directed edges (up to E edges)

This code solves the Minimum spanning tree problem, change the comparator function to solve the maximum spanning tree problem

The answer resides in the variable ans

Maximum Cardinality Bipartite Matching

Augmenting Path

Augmenting Path algorithm implemented with Greedy matching heuristic.

Worse case time complexity is O(NE). Realistically, it can handle up to a complete graph of N = 2000 or N = 10000, E = 1000000.

Initialise the struct with the number of nodes on the left A and the number of groups on the right B. Nodes on the left are labelled from 0 to A-1 while nodes on the right are labelled from 0 to B-1.

Use AddEdge(a, b) to add a possible matching between a node labelled a on the left to the node labelled b on the right.

Compute the maximum matching by calling MCBM(), the return value will be the maximum matching possible.

If you need to have the exact matching, call GetMatchings() after calling MCBM(). This function will return a vector of pairs, indicating which nodes on the left are matched with which nodes on the right.

Dinic's Algorithm

Under Construction, try Augmenting Path? or min cost max flow SPFA with cost 1.

Min Cut Max Flow

Edmonds-Karp Algorithm

Under Construction, try Push Relabel? or min cost max flow SPFA with cost 1.

Push Relabel

Push Relabel implemented with FIFO Queue and Gap Heuristic. Code requries O(N+E) memory and has a worse case O(N³) time complexity. Realistically, it can handle up to N = 10000, M = 100000 easily within 1 second.

Initialise the struct with the number of nodes in the graph. Nodes are labelled from 0 to N-1.

Use AddEdge(from, to, capacity) to add edges between nodes. Code uses adjacency list and supports multiple edges between a pair of nodes.

Source is defined as node S and the end is defined as node T.

Compute the Max Flow by calling MaxFlow(S, T), the return value will be the maximum flow.

Compute the Min Cut by calling MinCut(S, T), the return value will be a vector containing the list of nodes reachable from the source node after Min Cut.

Edges are all stored in vector E. Vector G is an adjacency list that stores the index of the edges in E.

For any edge with index ed, the index of it's backflow is index ed^1 as they are all inserted in pairs into E.

Min Cost Max Flow

In general, the approach is to use Edmonds-Karp algorithm, but swapping out the BFS for any shortest path algorithm (Eg: Bellman Ford, SPFA, Dijkstra).

Since SPFA always has a better run time than Bellman Ford, the below code does not implement Bellman Ford.

Using SPFA, worse case time complexity is minimum of O(NE*max_flow) or O(N²E²). However, usually SPFA runs much faster and is around O(kNE²) where k is a small constant.

Using Dijkstra, worse case time complexity is minmum of O(E log N * max_flow) or O(NE² log N). However, as Dijkstra cannot handle negative cycles, this is mitigated by adding potentials to keep all the edge weights non-negative. This potential is stored in vector phi

Initialise the struct with the number of nodes in the graph. Nodes are labelled from 0 to N-1.

Use AddEdge(from, to, cost, capacity) to add edges between nodes. Code uses adjacency list and supports multiple edges between a pair of nodes.

Source is defined as node S and the end is defined as node T.

Compute the Min Cost Max Flow by calling MinCost_SPFA(S, T, F) or MinCost_Dijkstra(S, T, F). For both caes, return value will be a pair. The first element would be the maximum flow possible from S to E, while the second element the minimum total cost to send this number of flows from S to T. F is an optional parameter, leave it blank to obtain the maximum possible flow.

Edges are all stored in vector E. Vector G is an adjacency list that stores the index of the edges in E.

For any edge with index ed, the index of it's backflow is index ed^1 as they are all inserted in pairs into E.