Groups
Category
Level
Tree diameter is the longest simple path in a tree and can be found with two BFS/DFS runs.
Tarjan’s algorithm finds all Strongly Connected Components (SCCs) of a directed graph in a single depth-first search using a stack.
A bridge is an edge whose removal increases the number of connected components; an articulation point is a vertex with the same property.
SPFA is a queue-based optimization of Bellman–Ford that only relaxes edges from vertices whose distance just improved.
The Lowest Common Ancestor (LCA) of two nodes in a rooted tree is the deepest node that is an ancestor of both.
An MST minimizes total edge weight over all spanning trees and has powerful properties such as the cut and cycle properties that guide correct, greedy construction.
Prim's algorithm builds a Minimum Spanning Tree (MST) by growing a tree from an arbitrary start vertex, always adding the lightest edge that connects the tree to a new vertex.
Kruskal’s algorithm builds a minimum spanning tree (MST) by sorting all edges by weight and greedily picking the next lightest edge that does not form a cycle.
Floyd–Warshall computes the shortest distances between all pairs of vertices in O(n^3) time using dynamic programming.
Dijkstra's algorithm finds shortest path distances from one source to all vertices when all edge weights are non-negative.
Bellman–Ford finds single-source shortest paths even when some edge weights are negative.
Dijkstra’s algorithm can be adapted to track the second shortest path by keeping the best and second-best distances per vertex.