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(N3) 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(N2E2). However, usually SPFA runs much faster and is around O(kNE2) where k is a small constant.
Using Dijkstra, worse case time complexity is minmum of O(E log N * max_flow) or O(NE2 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.