Graph Theory

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

• Pre-requisite for running algorithms.

• JDK16+ ( but with minute modifications can be run in JDK8+)
• Build Tool - Maven
• JUnit5 to run testcases.