Graph Algorithms

Compute shortest paths and detect negative weight cycles.

Find all maximal connected subgraphs in an undirected graph.

Detect cycles in directed and undirected graphs via 3-color DFS.

Find shortest paths from a source to all vertices in a weighted graph.

Construct Minimum Spanning Tree by sorting edges and using Union-Find.

Grow a Minimum Spanning Tree from an arbitrary root vertex.

Linear ordering of vertices in a DAG respecting directed dependencies.

Explore all neighbor nodes at the present depth before moving on to nodes at the next depth level.

Explore as far as possible along each branch before backtracking.