Comprehensive guide to 23+ essential graph algorithms with complexity analysis, use cases, and interactive visualizations.
Try Interactive PlatformExplores graph level by level, visiting all neighbors before moving deeper. Uses a queue data structure to maintain the order of exploration.
Explores as far as possible along each branch before backtracking. Uses a stack (or recursion) to track the exploration path.
Linear ordering of vertices in a directed acyclic graph (DAG) where each vertex appears before all vertices it points to.
Finds a path that visits every edge exactly once in an undirected graph. Exists when graph has exactly 0 or 2 vertices of odd degree.
Finds shortest paths from a source vertex to all other vertices in a weighted graph with non-negative edge weights.
Finds shortest paths from a source vertex and detects negative weight cycles. Works with negative edge weights.
Finds shortest paths between all pairs of vertices using dynamic programming with intermediate vertices.
Builds minimum spanning tree by growing from a single vertex, always adding the minimum weight edge that connects to a new vertex.
Builds minimum spanning tree by sorting all edges and using Union-Find to avoid cycles while adding minimum weight edges.
Builds minimum spanning tree using a parallel component-based approach, suitable for distributed computing environments.
Finds strongly connected components in directed graphs using DFS with low-link values and a stack.
Finds strongly connected components using two DFS passes: one on the original graph and one on the transpose graph.
Finds vertices whose removal would increase the number of connected components in an undirected graph.
Finds edges whose removal would increase the number of connected components in an undirected graph.
Determines if a graph can be colored with exactly two colors such that no adjacent vertices share the same color.
Detects the presence of cycles in both directed and undirected graphs using various techniques like DFS and Union-Find.
Finds a path that visits every vertex exactly once using backtracking and dynamic programming techniques.
Finds the shortest possible route that visits every city exactly once and returns to the starting point.
Assigns colors to vertices such that no two adjacent vertices share the same color, using the minimum number of colors.
Finds the largest complete subgraph where every pair of vertices is connected by an edge.
Determines if a graph is chordal (every cycle of length 4 or more has a chord - an edge connecting two non-adjacent vertices in the cycle).
Solves optimal assignment of workers to tasks using the Hungarian algorithm to minimize total cost.
Finds the maximum flow from a source to a sink in a flow network using algorithms like Ford-Fulkerson with augmenting paths.
Finds the minimum capacity cut that separates the source from the sink, closely related to maximum flow by the max-flow min-cut theorem.
Experience interactive visualizations and step-by-step execution of all these algorithms.
Launch Interactive Platform