network/tarjans_algorithm library

🔗 Tarjan's Algorithm (Bridges and Articulation Points)

Finds all bridges (critical edges) and articulation points (critical nodes) in an undirected graph using depth-first search with low-link values.

  • Time Complexity: O(V + E) where V is vertices, E is edges
  • Space Complexity: O(V) for DFS stack and arrays
  • Optimality: Guaranteed to find all bridges and articulation points
  • Completeness: Always terminates and finds all critical components
  • Applications: Network reliability, social network analysis, circuit design

Tarjan's algorithm uses DFS to identify critical components by tracking discovery times and low-link values for each node.

Example:

final graph = <int, List<int>>{
  0: [1, 2],
  1: [0, 2],
  2: [0, 1, 3],
  3: [2, 4],
  4: [3],
};
final result = tarjansAlgorithm(graph);
print('Bridges: ${result.bridges}'); // [[2, 3]]
print('Articulation Points: ${result.articulationPoints}'); // [2]

Classes

Bridge<T>
Represents a bridge (critical edge) in the graph
TarjansDetailedResult<T>
Enhanced Tarjan's algorithm with detailed analysis
TarjansResult<T>
Result of Tarjan's algorithm containing bridges and articulation points

Functions

max<T extends num>(T a, T b) → T
Utility function for finding maximum of two numbers
min<T extends num>(T a, T b) → T
Utility function for finding minimum of two numbers
tarjansAlgorithm<T>(Map<T, List<T>> graph) → TarjansResult<T>
Tarjan's algorithm for finding bridges and articulation points
tarjansAlgorithmDetailed<T>(Map<T, List<T>> graph) → TarjansDetailedResult<T>
Enhanced Tarjan's algorithm with detailed analysis