Algorithms & Complexity

The Graph class bundles traversal, optimization, and analysis routines. This page highlights what each algorithm does, its prerequisites, and the expected complexity (worst-case big-O based on vertex count |V| and edge count |E|).

API	Description	Prerequisites	Complexity
depthFirstSearch(start, stack?)	Standard DFS that records visitation order; optionally fills a stack for Kosaraju-style passes.	Comparator must order vertices deterministically when ties occur.	O(|V| + |E|)
breadthFirstSearch(start)	BFS returning vertices in discovery order.	Graph can be directed or undirected.	O(|V| + |E|)
shortestPath(from, to)	Moore–Bellman–Ford variant returning a List of vertices along the shortest path.	Handles negative weights but fails if negative cycles exist; call checkForNegativeCycles() first for safety.	O(|V|·|E|)
kShortestPaths(from, to, k)	Generates the k shortest simple paths using a Yen-inspired approach.	Comparator must be supplied; graph should not contain negative cycles.	O(k·|V|·(|E| + |V| \log |V|)) (approx.).
minimalSpanningTree()	Builds a minimum spanning tree (Kruskal) for undirected graphs or minimum branching for directed.	Requires a connected undirected graph for MST semantics.	O(|E| \log |V|)
topologicalSorting()	Returns a valid topological order for DAGs.	Graph must be acyclic and directed.	O(|V| + |E|)
parallelTopologicalSorting()	Produces layered ordering suitable for parallel execution or visualization.	DAG required.	O(|V| + |E|)
connectedComponents()	Returns each weakly connected component as its own graph instance.	Works on directed/undirected graphs.	O(|V| + |E|)
strongConnectedComponents()	Kosaraju-style SCC detection returning an array of strongly connected subgraphs.	Graph must be directed.	O(|V| + |E|)
checkForCycles() / inferCycles()	Detects whether cycles exist and optionally collects them.	Works for mixed graphs; inferCycles() can be expensive on dense graphs.	O(|V| + |E|) detection; enumeration varies.
checkForNegativeCycles()	Uses Bellman–Ford relaxations plus one extra pass to spot negative cycles.	Only meaningful for weighted directed graphs.	O(|V|·|E|)

Patterns & tips

• Favor graph.createEdge()/addEdge() so vertex adjacency stays consistent; algorithms depend on the incomingEdges/outgoingEdges sets maintained there.
• Set graph.comparator before calling algorithms that rely on deterministic ordering (DFS, topological sorting, k shortest paths). Tests provide an example comparator in test/factories/graph.ts.
• See GraphFactory as an example for creating dense/sparse graphs when benchmarking.
• For performance-sensitive workflows, profile the specific algorithm on representative graphs. The coverage/ folder plus Vitest snapshots can help you capture baseline metrics.