Implementation of well-known Graph theory algorithms & their applications in Java Programming language.
- Breadth First Search - Shortest Path --> TestCase
- Depth First Search - Recursive With Adjaceny List Representation --> TestCase
- Depth First Search - Count the number of components in a given graph -->TestCase
- Dungeon Problem in 2D - Count the steps to Exit. Using Adjacency Matrix --> TestCase
- Leaf Sum - Calculate sum of the values in all leaf nodes in a rooted tree --> TestCase
- Height of Tree - Find the height of a binary tree --> TestCase
- Rooting a tree - Given an undirected graph and a designated root node, transform to a Rooted Tree with DFS recursively --> TestCase
- Center(s) of a Tree - Given an undirected graph, acyclic graph - find the center(s) of the tree --> TestCase
- Tree Isomorphism - Whether two trees given as undirected graphs, are structurally same - AHO Algorithm used for encoding --> TestCase
- Topological Sort - Using DFS Recursion --> TestCase
- Single Source Shortest Path - Using topological sort with Directed Acyclic Weighted Graph (DAG) --> TestCase
- Single Source Shortest Path - Dijkstra's Lazy Approach Using Priority Queue - Non-negative weights (DAG) --> TestCase
- Min Heap based Priority Queue --> TestCase
- Min Heap based Indexed Priority Queue --> TestCase
- Single Source Shortest Path - Dijkstra's Eager Approach - Uses Indexed Priority Queue - Non-Negative Weights (DAG) --> TestCase
- Single Source Shortest Path - Bellman Ford -Edge List Representation - Works for Negative Weights, Detects Negative Cycle (DAG) --> TestCase
- All Pair Shortest Path - Floyd Warshall Algorithm With Path Reconstruction, Detects and Propogates Vertices in the Negative Cycle --> TestCase
- Find Bridges or cut edge in a graph with Adj List --> TestCase
- Find Articulation Point in a graph --> TestCase
- Find Strongly Connected Components in Directed Graph - Tarjans Algorithm --> TestCase
- JDK16+ ( but with minute modifications can be run in JDK8+)
- Build Tool - Maven
- JUnit5 to run testcases.