# 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 non-negative edge weights. `O(|E| + |V| log |V|)`

• #### 02.07 – Bellman-Ford Algorithm

Finds the Single Source Shortest Path (SSSP) from one node to all other nodes on any graph. `O(|V||E|)`

• #### 02.08 – Floyd-Warshall Algorithm

Finds the All Pairs Shortest Path (APSP) for any pair of nodes on any graph. `O(|V|^3)`

• ### 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.

• ### 10 – Miscellaneous

• #### 10.01 – Binary Search

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