C :: A handbook of Algorithms and Data Structures

---

• Assignment Algorithms for Weighted Maximum Cardinality Bipartite Matching

  • Hungarian Algorithm using the Hopcroft-Karp Algorithm as a subroutine for the Munkres Assignment Problem

  ---

• String Searching Algorithms

  • Trie Aho-Corasick Automaton used by the fgrep command of UNIX

  • Z-algorithm for linear pattern matching

  • Knutt-Morris-Pratt algorithm for linear pattern matching

  ---

• Topological Sort algorithms

  • Kahn's algorithm for topologically sorting a graph

  • Using a Depth First Search for topologically sorting a graph

  ---

• Graph Algorithms

  • Johnson's Algorithm

  • Kosaraju's Algorithm for finding Strongly Connected Components in a graph

  • Tarjan's Algorithm for finding Strongly Connected Components in a graph

  • Welsh-Powell Algorithm for Graph Coloring

  • Dijkstra's Algorithm using a binary heap

  • Dijkstra's Algorithm using linear search

  • Bellman Ford's Routing Algorithm

  • Floyd Warshall's Algorithm

  ---

• Data Structures

  • Sparse Table for calculating range queries

  • Union Find (popularly used in Minimum Spanning Tree algorithms)

  • Fenwick(Binary Indexed) Trees for range queries

  • Segment Trees for range queries

  • Trie

  ---

• Tree Algorithms

  • Lowest Common Ancestor Algorithms

    • Eulerian Tour for LCA using Sparse Table coupled with Farach-Colton and Bender Optimization

    • Binary Lifting for LCA using Dynamic Programming

  ---

  • Tree centering Algorithm

  • Tree Rooting Algorithm

  • AHU(Aho - Hopcroft - Ullman) Encoding

  ---

• Flow Algorithms

  • Ford-Fulkerson coupled with Capacity Scalling using DFS

  • Edmonds Karp coupled with Capacity Scalling using BFS

  • Dinic's Algorithm coupled with Capacity Scalling using DFS//BFS

  • Push Relabel Algorithm

  ---

• Maximum Cardinality Bipartite Matching Algorithms

  • Max-Flow Algorithm for MCBM

  • Hopcroft-Karp for MCBM

  ---