Algorithms and Data Structures Archive
Contents

01 – Data Structures

01.01 – Disjoint Sets
Data Structure for operation and maintainance on disjoint sets over elements also often called Disjoint Set Union (DSU) or Union Find.
O(α(n))


02 – Graphs

02.01 – Depth First Search (DFS)
Depth First Search (DFS) is a graph traversal algorithm starting at a node and exploring one branch as far as possible before backtracking.
O(V + E)

02.02 – Breadth First Search (BFS)
Breadth First Search (BFS) is a graph traversal algorithm starting at a node and explores all nodes at the present depth before moving on to the nodes at the next depth level.
O(V + E)

02.03 – Topological Sort (TS)
Graph traversal algorithm on a directed graph resulting in a topological order where any predecessor of a node is ordered before any of it’s postdecessors.
O(V + E)

02.04 – Kruskal’s Algorithm
Constructs a MST of a connected graph by repeatedly adding the next shortest edge not already contained in the subgraph until we have a MST.
O(E log E)

02.05 – Prim’s Algorithm
Constructs a MST of a connected graph by repeatedly adding the shortest edge to the subgraph which connects a node already in the subgraph to a node outside of it until we have a MST.
O(E + V log V)

02.06 – Dijkstra’s Algorithm
Finds the Single Source Shortest Path (SSSP) from one node to all other nodes on any graph with nonnegative edge weights.
O(E + V log V)

02.07 – BellmanFord Algorithm
Finds the Single Source Shortest Path (SSSP) from one node to all other nodes on any graph.
O(VE)

02.08 – FloydWarshall Algorithm
Finds the All Pairs Shortest Path (APSP) for any pair of nodes on any graph.
O(V^3)


03 – Trees

04 – Maximum Flow

05 – Brute Force
Technique of systematically iterating over all solution candidates until one satisfies the solution requirements.

06 – Greedy
Technique of approximating the optimal solution to a problem by choosing optimal solutions for its subproblems.

07 – Dynamic Programming
Technique of solving a problem by recursively dividing it into subproblems. After solving a subproblem it’s solution is cached for later reuse in case the same subproblem comes up again.

08 – Number Theory

09 – Geometry

10 – Miscellaneous

10.01 – Binary Search
Algorithm used for finding a specific value/element in an ordered interval range.
O(log n)
